# Publications

This book constitutes the proceedings of the 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019, held in Kazan, Russia, in July 2019.

The 24 full papers and 10 short papers were carefully reviewed and selected from 134 submissions (of which 21 papers were rejected without being reviewed). The papers are organized in topical sections on general topics of data analysis; natural language processing; social network analysis; analysis of images and video; optimization problems on graphs and network structures; analysis of dynamic behaviour through event data.

For a graph *G* and a positive integer *k*, a subset *C* of vertices of *G* is called a *k*-path vertex cover if *C* intersects all paths of *k* vertices in *G*. The cardinality of a minimum *k*-path vertex cover is denoted by *β_{**P_**k*}(*G*). For a graph *G* and a positive integer *k*, a subset *M* of pairwise vertex-disjoint paths of *k* vertices in *G* is called a *k*-path packing. The cardinality of a maximum *k*-path packing is denoted by *μ**_{P_**k*}(*G*). In this paper, we describe some graphs, having equal values of *β**_{P_**k}* and *μ**{P**_k}*, for *k*≥5, and present polynomial-time algorithms of finding a minimum *k*-path vertex cover and a maximum *k*-path packing in such graphs.

The goal of the study is to increase the computation efficiency of the face recognition that uses feature vectors to describe facial images on photos and videos. These high-dimensional feature vectors are nowadays produced by convolutional neural networks. The methods to aggregate the features generated for each video frame are used to process the video sequences. A novel hierarchical recognition algorithm is proposed. In contrast to known approaches our algorithm seeks the nearest neighbors only among reference images of most reliable classes selected at the preceding stage to carry out the sequential analysis of a more detailed description level (with a greater dimensionality of the feature vector). At each stage principal components are compared, the number of the components being chosen according to a given portion of explained variations. Datasets like Labeled Faces in the Wild, YouTubeFaces, IAPRA, Jenus Benchmark C and different neural-net face descriptors are used to compare the algorithm with other methods. In contrast with the conventional nearest-neighbor method, the proposed approach is shown to allow a 2- to 16-times reduction of the classifier running time.

Independent domination is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NP-hardness of the weighted version in a certain class to the unweighted case. Second, we strengthen polynomial-time solvability of the unweighted version in the class of P2+P3-free graphs to the weighted case. This result is tight in the sense that both versions are NP-hard in the class of P3+P3-free graphs, i.e. P3+P3 is a minimal graph forbidding of which produces an NP-hard case for both versions of the problem.

This proceedings presents the result of the 8th International Conference in Network Analysis, held at the Higher School of Economics, Moscow, in May 2018. The conference brought together scientists, engineers, and researchers from academia, industry, and government. Contributions in this book focus on the development of network algorithms for data mining and its applications. Researchers and students in mathematics, economics, statistics, computer science, and engineering find this collection a valuable resource filled with the latest research in network analysis. Computational aspects and applications of large-scale networks in market models, neural networks, social networks, power transmission grids, maximum clique problem, telecommunication networks, and complexity graphs are included with new tools for efficient network analysis of large-scale networks. Machine learning techniques in network settings including community detection, clustering, and biclustering algorithms are presented with applications to social network analysis.

In the current paper we provide a proof of NP-completeness for the Cell Formation Problem (CFP) with the fractional grouping efficacy objective function. First the CFP with a linear objective function is considered. Following the ideas of Pinheiro et al. (2016) we show that it is equivalent to the Bicluster Graph Editing Problem (BGEP), which is known to be NP-complete due to the reduction from the 3-Exact 3-Cover Problem – 3E3CP (Amit, 2004). Then we suggest a polynomial reduction of the CFP with the linear objective to the CFP with the grouping efficacy objective. It proves the NP-completeness of this fractional CFP formulation. Along with the NP-status our paper presents important connections of the CFP with the BGEP and 3E3CP. Such connections could be used for ”transferring” of known theoretical properties, efficient algorithms, polynomial cases, and other features of well-studied graph editing and exact covering problems to the CFP.

In the present paper we prove that frames of one-dimensional separatrices in basins of sources of structurally stable 3-diffeomorhisms with two-dimensional expanding attractor are trivially embedded. This result plays an important part in the classification of such systems. The classification was given by V. Grines and E. Zhuzhoma with assumption that all one-dimensional separatrices are trivially embedded into the ambient manifold but the proof of the assumption was never given. Thus, the present paper is a necessary and nontrivial element of the classification of structurally stable diffeomorphisms with codimension one expanding attractors.

We consider a class of sequential network interdiction problem settings where the interdictor has incomplete initial information about the network while the evader has complete knowledge of the network including its structure and arc costs. In each decision epoch, the interdictor can block (for the duration of the epoch) at most k arcs known to him. By observing the evader's actions, the interdictor learns about the network structure and costs and thus, can adjust his actions in subsequent decision epochs. It is known from the literature that if the evader is greedy (i.e., she uses the shortest available path in each decision epochs), then under some assumptions the greedy interdiction policies that block k-most vital arcs in each epoch are efficient and have a finite regret. In this paper, we consider the evader's perspective and explore strategic evasion policies under the assumption that the interdictor is greedy. We first study the theoretical computational complexity of the evader's problem. Then we derive basic constructive properties of optimal evasion policies for two decision epochs when the interdictor has no initial information about the network structure. These properties are then exploited for the design of a heuristic algorithm for a strategic evader in a general setting with an arbitrary time horizon and any initial information available to the interdictor. Our computational experiments demonstrate that the proposed heuristic consistently outperforms the greedy evasion policy on several classes of synthetic network instances under perfect and noisy information feedbacks. Finally, some interesting insights from our theoretical and computational results conclude the paper.

If the training data set in image recognition task is not very large, the feature extraction with a convolutional neural network is usually applied. Here, we focus on the nonparametric classification of extracted feature vectors using the probabilistic neural network (PNN). The latter is characterized by the high runtime and memory space complexity. We propose to overcome these drawbacks by replacing the exponential activation function in the Gaussian kernel to the complex exponential functions. Such complex nonlinearities make it possible to accurately approximate the unknown density function using the network with the number of neurons proportional to only cubic root of the database size. As a result, the proposed approach decreases the runtime and memory complexities of the PNN without losing its main advantages, namely, fast training and convergence to the Bayesian decision. In the experimental study, we describe a protocol for comparing recognition methods using the well-known visual object category data sets in the context of the small sample size problem. It has been experimentally shown that our approach rapidly obtains accurate decisions when compared to the known classifiers including the baseline PNN.

For any *n*, in the set of *n*-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets.

In this paper we consider several efficient techniques for multi-label classification of a set of images. We propose the two-stage approach. First, we perform transfer learning on a pretrained convolutional neural network in order to use it as a feature extractor. Next, the feature vectors of each image from a given input set are combined into a single vector using the modification of the attention-based neural aggregation module. In the experimental study we examine the classification of the user's interests based on the photos of products purchased by this user using the Amazon Product Home and Kitchen dataset. It was shown that one of the most highest F1-measure (0.87 for 15 recommendations) is achieved for one-layer attention block with squeezed visual features. It is emphasized that the resulting model including the MobileNet feature extractor has 16 Mb size only.

In this paper, a deep learning method study is conducted to solve a new multiclass text classification problem, identifying user interests by text messages. We used an original dataset of almost 90 thousand forum text messages, labeled for ten interests. We experimented with different modern neural network architectures: recurrent and convolutional, as well as simpler feedforward networks. Classification accuracy was evaluated for different architectures, text representations, and sets of miscellaneous parameters.

We developed a new method for measuring the pitch frequency of speech signals with elevated noise immunity. The problem of protection against intense background noise is solved in this method by the frequency selection of vocalized segments of speech signals according to a scheme with comb filter of interperiodic accumulation. The efficiency of the method is analyzed both theoretically and experimentally with the help of a multichannel frequency meter intended for the acoustic speech analysis. It is shown that, for a signal-to-noise ratio of 10 dB and higher, the error of the method does not exceed 2%.

This book constitutes the post-conference proceedings of the 8th International Conference on Analysis of Images, Social Networks and Texts, AIST 2019, held in Kazan, Russia, in July 2019.

The 27 full and 8 short papers were carefully reviewed and selected from 134 submissions (of which 21 papers were automatically rejected without being reviewed). The papers are organized in topical sections on general topics of data analysis; natural language processing; social network analysis; analysis of images and video; optimization problems on graphs and network structures; and analysis of dynamic behavior through event data.

We consider reformulations of a class of bilevel linear integer programs as equivalent linear mixed-integer programs (linear MIPs). Themost common technique to reformulate such programs as a single-level problem is to replace the lower-level linear optimization problem by Karush–Kuhn–Tucker (KKT) optimality conditions. Employing the strong duality (SD) property of linear programs is an alternative method to perform such transformations. In this note, we describe two SD-based reformulations where the key idea is to exploit the binary expansion of upper-level integer variables. We compare the performance of an offthe- shelfMIP solver with the SD-based reformulations against the KKT-based one and show that the SD-based approaches can lead to orders of magnitude reduction in computational times for certain classes of instances

In Chirkov et al., (2019), classes of *conic* and *discrete conic* functions were introduced. In this paper we use the term *convic* instead *conic*. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. In Chirkov et al., (2019), the lower bound 3^{n-1} log(R) for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some n-dimensional ball with radius R was obtained. But the problem of the existence of a polynomial (in log(R) for fixed n) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses 2^{n^2 log(n)} log(R) calls to the comparison oracle and has 2^{n^2 log(n)} poly(log(R)) bit complexity.

The authors consider the problem of automatic detection of private scanned documents based on text recognition with deep neural networks. The paper suggests implementing a two-phase approach with the first stage which includes efficient EAST text detection and recognition using Tesseract OCR Engine. Secondly, the authors classify the privacy of a scanned document by deep neural networks applied to the extracted text. After that, a special dataset is gathered in order to train these networks. The experiments show that using OCR Engine for both text detection and segmentation ends up with relatively poor identification of private documents when compared to preliminary text detection with EAST method. Moreover, conventional keyword spotting using the list of sensitive words is less accurate when compared to neural network-based methods. Finally, it was demonstrated that the classification of a bag of most frequent words outperforms traditional text classification techniques with LSTM and convolutional networks.

Recurrent neural networks have proved to be an effective method for statistical language modeling. However, in practice their memory and run-time complexity are usually too large to be implemented in real-time offline mobile applications. In this paper we consider several compression techniques for recurrent neural networks including Long–Short Term Memory models. We make particular attention to the high-dimensional output problem caused by the very large vocabulary size. We focus on effective compression methods in the context of their exploitation on devices: pruning, quantization, and matrix decomposition approaches (low-rank factorization and tensor train decomposition, in particular). For each model we investigate the trade-off between its size, suitability for fast inference and perplexity. We propose a general pipeline for applying the most suitable methods to compress recurrent neural networks for language modeling. It has been shown in the experimental study with the Penn Treebank (PTB) dataset that the most efficient results in terms of speed and compression–perplexity balance are obtained by matrix decomposition techniques.