Elif Vural

Eylem Tugce Guneyi, Berkay Yaldiz, Abdullah Canbolat et al.

The modeling of time-varying graph signals as stationary time-vertex stochastic processes permits the inference of missing signal values by efficiently employing the correlation patterns of the process across different graph nodes and time instants. In this study, we propose an algorithm for computing graph autoregressive moving average (graph ARMA) processes based on learning the joint time-vertex power spectral density of the process from its incomplete realizations for the task of signal interpolation. Our solution relies on first roughly estimating the joint spectrum of the process from partially observed realizations and then refining this estimate by projecting it onto the spectrum manifold of the graph ARMA process through convex relaxations. The initially missing signal values are then estimated based on the learnt model. Experimental results show that the proposed approach achieves high accuracy in time-vertex signal estimation problems.

Melih Can Zerin, Elif Vural, Ali Özgür Yılmaz

In this paper, we propose an algorithm for downlink (DL) channel covariance matrix (CCM) estimation for frequency division duplexing (FDD) massive multiple-input multiple-output (MIMO) communication systems with base station (BS) possessing a uniform linear array (ULA) antenna structure. We consider a setting where the UL CCM is mapped to DL CCM by a mapping function. We first present a theoretical error analysis of learning a nonlinear embedding by constructing a mapping function, which points to the importance of the Lipschitz regularity of the mapping function for achieving high estimation performance. Then, based on the theoretical ground, we propose a representation learning algorithm as a solution for the estimation problem, where Gaussian RBF kernel interpolators are chosen to map UL CCMs to their DL counterparts. The proposed algorithm is based on the optimization of an objective function that fits a regression model between the DL CCM and UL CCM samples in the training dataset and preserves the local geometric structure of the data in the UL CCM space, while explicitly regulating the Lipschitz continuity of the mapping function in light of our theoretical findings. The proposed algorithm surpasses benchmark methods in terms of three error metrics as shown by simulations.

Elif Vural, Huseyin Karaca

Domain adaptation seeks to leverage the abundant label information in a source domain to improve classification performance in a target domain with limited labels. While the field has seen extensive methodological development, its theoretical foundations remain relatively underexplored. Most existing theoretical analyses focus on simplified settings where the source and target domains share the same input space and relate target-domain performance to measures of domain discrepancy. Although insightful, these analyses may not fully capture the behavior of modern approaches that align domains into a shared space via feature transformations. In this paper, we present a comprehensive theoretical study of domain adaptation algorithms based on domain alignment. We consider the joint learning of domain-aligning feature transformations and a shared classifier in a semi-supervised setting. We first derive generalization bounds in a broad setting, in terms of covering numbers of the relevant function classes. We then extend our analysis to characterize the sample complexity of domain-adaptive neural networks employing maximum mean discrepancy (MMD) or adversarial objectives. Our results rely on a rigorous analysis of the covering numbers of these architectures. We show that, for both MMD-based and adversarial models, the sample complexity admits an upper bound that scales quadratically with network depth and width. Furthermore, our analysis suggests that in semi-supervised settings, robustness to limited labeled target data can be achieved by scaling the target loss proportionally to the square root of the number of labeled target samples. Experimental evaluation in both shallow and deep settings lends support to our theoretical findings.

Osman Furkan Kar, Gülce Turhan, Elif Vural

While a common assumption in graph signal analysis is the smoothness of the signals or the band-limitedness of their spectrum, in many instances the spectrum of real graph data may be concentrated at multiple regions of the spectrum, possibly including mid-to-high-frequency components. In this work, we propose a novel graph signal model where the signal spectrum is represented through the combination of narrowband kernels in the graph frequency domain. We then present an algorithm that jointly learns the model by optimizing the kernel parameters and the signal representation coefficients from a collection of graph signals. Our problem formulation has the flexibility of permitting the incorporation of signals possibly acquired on different graphs into the learning algorithm. We then theoretically study the signal reconstruction performance of the proposed method, by also elaborating on when joint learning on multiple graphs is preferable to learning an individual model on each graph. Experimental results on several graph data sets shows that the proposed method offers quite satisfactory signal interpolation accuracy in comparison with a variety of reference approaches in the literature.

Abdullah Canbolat, Elif Vural

Stationary graph process models are commonly used in the analysis and inference of data sets collected on irregular network topologies. While most of the existing methods represent graph signals with a single stationary process model that is globally valid on the entire graph, in many practical problems, the characteristics of the process may be subject to local variations in different regions of the graph. In this work, we propose a locally stationary graph process (LSGP) model that aims to extend the classical concept of local stationarity to irregular graph domains. We characterize local stationarity by expressing the overall process as the combination of a set of component processes such that the extent to which the process adheres to each component varies smoothly over the graph. We propose an algorithm for computing LSGP models from realizations of the process, and also study the approximation of LSGPs locally with WSS processes. Experiments on signal interpolation problems show that the proposed process model provides accurate signal representations competitive with the state of the art.

Semih Kaya, Elif Vural

While many approaches exist in the literature to learn low-dimensional representations for data collections in multiple modalities, the generalizability of multi-modal nonlinear embeddings to previously unseen data is a rather overlooked subject. In this work, we first present a theoretical analysis of learning multi-modal nonlinear embeddings in a supervised setting. Our performance bounds indicate that for successful generalization in multi-modal classification and retrieval problems, the regularity of the interpolation functions extending the embedding to the whole data space is as important as the between-class separation and cross-modal alignment criteria. We then propose a multi-modal nonlinear representation learning algorithm that is motivated by these theoretical findings, where the embeddings of the training samples are optimized jointly with the Lipschitz regularity of the interpolators. Experimental comparison to recent multi-modal and single-modal learning algorithms suggests that the proposed method yields promising performance in multi-modal image classification and cross-modal image-text retrieval applications.

Yusuf Yigit Pilavci, Eylem Tugce Guneyi, Cemil Cengiz et al.

In this paper we propose a domain adaptation algorithm designed for graph domains. Given a source graph with many labeled nodes and a target graph with few or no labeled nodes, we aim to estimate the target labels by making use of the similarity between the characteristics of the variation of the label functions on the two graphs. Our assumption about the source and the target domains is that the local behaviour of the label function, such as its spread and speed of variation on the graph, bears resemblance between the two graphs. We estimate the unknown target labels by solving an optimization problem where the label information is transferred from the source graph to the target graph based on the prior that the projections of the label functions onto localized graph bases be similar between the source and the target graphs. In order to efficiently capture the local variation of the label functions on the graphs, spectral graph wavelets are used as the graph bases. Experimentation on various data sets shows that the proposed method yields quite satisfactory classification accuracy compared to reference domain adaptation methods.

Eda Bayram, Dorina Thanou, Elif Vural et al.

Structure inference is an important task for network data processing and analysis in data science. In recent years, quite a few approaches have been developed to learn the graph structure underlying a set of observations captured in a data space. Although real-world data is often acquired in settings where relationships are influenced by a priori known rules, such domain knowledge is still not well exploited in structure inference problems. In this paper, we identify the structure of signals defined in a data space whose inner relationships are encoded by multi-layer graphs. We aim at properly exploiting the information originating from each layer to infer the global structure underlying the signals. We thus present a novel method for combining the multiple graphs into a global graph using mask matrices, which are estimated through an optimization problem that accommodates the multi-layer graph information and a signal representation model. The proposed mask combination method also estimates the contribution of each graph layer in the structure of signals. The experiments conducted both on synthetic and real-world data suggest that integrating the multi-layer graph representation of the data in the structure inference framework enhances the learning procedure considerably by adapting to the quality and the quantity of the input data.

Elif Vural

Traditional machine learning algorithms assume that the training and test data have the same distribution, while this assumption does not necessarily hold in real applications. Domain adaptation methods take into account the deviations in the data distribution. In this work, we study the problem of domain adaptation on graphs. We consider a source graph and a target graph constructed with samples drawn from data manifolds. We study the problem of estimating the unknown class labels on the target graph using the label information on the source graph and the similarity between the two graphs. We particularly focus on a setting where the target label function is learnt such that its spectrum is similar to that of the source label function. We first propose a theoretical analysis of domain adaptation on graphs and present performance bounds that characterize the target classification error in terms of the properties of the graphs and the data manifolds. We show that the classification performance improves as the topologies of the graphs get more balanced, i.e., as the numbers of neighbors of different graph nodes become more proportionate, and weak edges with small weights are avoided. Our results also suggest that graph edges between too distant data samples should be avoided for good generalization performance. We then propose a graph domain adaptation algorithm inspired by our theoretical findings, which estimates the label functions while learning the source and target graph topologies at the same time. The joint graph learning and label estimation problem is formulated through an objective function relying on our performance bounds, which is minimized with an alternating optimization scheme. Experiments on synthetic and real data sets suggest that the proposed method outperforms baseline approaches.

Mehmet Pilanci, Elif Vural

A common assumption in semi-supervised learning with graph models is that the class label function varies smoothly on the data graph, resulting in the rather strict prior that the label function has low-frequency content. Meanwhile, in many classification problems, the label function may vary abruptly in certain graph regions, resulting in high-frequency components. Although the semi-supervised estimation of class labels is an ill-posed problem in general, in several applications it is possible to find a source graph on which the label function has similar frequency content to that on the target graph where the actual classification problem is defined. In this paper, we propose a method for domain adaptation on graphs motivated by these observations. Our algorithm is based on learning the spectrum of the label function in a source graph with many labeled nodes, and transferring the information of the spectrum to the target graph with fewer labeled nodes. While the frequency content of the class label function can be identified through the graph Fourier transform, it is not easy to transfer the Fourier coefficients directly between the two graphs, since no one-to-one match exists between the Fourier basis vectors of independently constructed graphs in the domain adaptation setting. We solve this problem by learning a transformation between the Fourier bases of the two graphs that flexibly ``aligns'' them. The unknown class label function on the target graph is then reconstructed such that its spectrum matches that on the source graph while also ensuring the consistency with the available labels. The proposed method is tested in the classification of image, online product review, and social network data sets. Comparative experiments suggest that the proposed algorithm performs better than recent domain adaptation methods in the literature in most settings.

Jeremy Aghaei Mazaheri, Elif Vural, Claude Labit et al.

Sparse representations using overcomplete dictionaries have proved to be a powerful tool in many signal processing applications such as denoising, super-resolution, inpainting, compression or classification. The sparsity of the representation very much depends on how well the dictionary is adapted to the data at hand. In this paper, we propose a method for learning structured multilevel dictionaries with discriminative constraints to make them well suited for the supervised pixelwise classification of images. A multilevel tree-structured discriminative dictionary is learnt for each class, with a learning objective concerning the reconstruction errors of the image patches around the pixels over each class-representative dictionary. After the initial assignment of the class labels to image pixels based on their sparse representations over the learnt dictionaries, the final classification is achieved by smoothing the label image with a graph cut method and an erosion method. Applied to a common set of texture images, our supervised classification method shows competitive results with the state of the art.

Cem Ornek, Elif Vural

The recovery of the intrinsic geometric structures of data collections is an important problem in data analysis. Supervised extensions of several manifold learning approaches have been proposed in the recent years. Meanwhile, existing methods primarily focus on the embedding of the training data, and the generalization of the embedding to initially unseen test data is rather ignored. In this work, we build on recent theoretical results on the generalization performance of supervised manifold learning algorithms. Motivated by these performance bounds, we propose a supervised manifold learning method that computes a nonlinear embedding while constructing a smooth and regular interpolation function that extends the embedding to the whole data space in order to achieve satisfactory generalization. The embedding and the interpolator are jointly learnt such that the Lipschitz regularity of the interpolator is imposed while ensuring the separation between different classes. Experimental results on several image data sets show that the proposed method outperforms traditional classifiers and the supervised dimensionality reduction algorithms in comparison in terms of classification accuracy in most settings.

Elif Vural, Christine Guillemot

Supervised manifold learning methods learn data representations by preserving the geometric structure of data while enhancing the separation between data samples from different classes. In this work, we propose a theoretical study of supervised manifold learning for classification. We consider nonlinear dimensionality reduction algorithms that yield linearly separable embeddings of training data and present generalization bounds for this type of algorithms. A necessary condition for satisfactory generalization performance is that the embedding allow the construction of a sufficiently regular interpolation function in relation with the separation margin of the embedding. We show that for supervised embeddings satisfying this condition, the classification error decays at an exponential rate with the number of training samples. Finally, we examine the separability of supervised nonlinear embeddings that aim to preserve the low-dimensional geometric structure of data based on graph representations. The proposed analysis is supported by experiments on several real data sets.

Julio Cesar Ferreira, Elif Vural, Christine Guillemot

Local learning of sparse image models has proven to be very effective to solve inverse problems in many computer vision applications. To learn such models, the data samples are often clustered using the K-means algorithm with the Euclidean distance as a dissimilarity metric. However, the Euclidean distance may not always be a good dissimilarity measure for comparing data samples lying on a manifold. In this paper, we propose two algorithms for determining a local subset of training samples from which a good local model can be computed for reconstructing a given input test sample, where we take into account the underlying geometry of the data. The first algorithm, called Adaptive Geometry-driven Nearest Neighbor search (AGNN), is an adaptive scheme which can be seen as an out-of-sample extension of the replicator graph clustering method for local model learning. The second method, called Geometry-driven Overlapping Clusters (GOC), is a less complex nonadaptive alternative for training subset selection. The proposed AGNN and GOC methods are evaluated in image super-resolution, deblurring and denoising applications and shown to outperform spectral clustering, soft clustering, and geodesic distance based subset selection in most settings.

Elif Vural, Christine Guillemot

Supervised manifold learning methods for data classification map data samples residing in a high-dimensional ambient space to a lower-dimensional domain in a structure-preserving way, while enhancing the separation between different classes in the learned embedding. Most nonlinear supervised manifold learning methods compute the embedding of the manifolds only at the initially available training points, while the generalization of the embedding to novel points, known as the out-of-sample extension problem in manifold learning, becomes especially important in classification applications. In this work, we propose a semi-supervised method for building an interpolation function that provides an out-of-sample extension for general supervised manifold learning algorithms studied in the context of classification. The proposed algorithm computes a radial basis function (RBF) interpolator that minimizes an objective function consisting of the total embedding error of unlabeled test samples, defined as their distance to the embeddings of the manifolds of their own class, as well as a regularization term that controls the smoothness of the interpolation function in a direction-dependent way. The class labels of test data and the interpolation function parameters are estimated jointly with a progressive procedure. Experimental results on face and object images demonstrate the potential of the proposed out-of-sample extension algorithm for the classification of manifold-modeled data sets.

Elif Vural, Pascal Frossard

The computation of the geometric transformation between a reference and a target image, known as registration or alignment, corresponds to the projection of the target image onto the transformation manifold of the reference image (the set of images generated by its geometric transformations). It, however, often takes a nontrivial form such that the exact computation of projections on the manifold is difficult. The tangent distance method is an effective algorithm to solve this problem by exploiting a linear approximation of the manifold. As theoretical studies about the tangent distance algorithm have been largely overlooked, we present in this work a detailed performance analysis of this useful algorithm, which can eventually help its implementation. We consider a popular image registration setting using a multiscale pyramid of lowpass filtered versions of the (possibly noisy) reference and target images, which is particularly useful for recovering large transformations. We first show that the alignment error has a nonmonotonic variation with the filter size, due to the opposing effects of filtering on both manifold nonlinearity and image noise. We then study the convergence of the multiscale tangent distance method to the optimal solution. We finally examine the performance of the tangent distance method in image classification applications. Our theoretical findings are confirmed by experiments on image transformation models involving translations, rotations and scalings. Our study is the first detailed study of the tangent distance algorithm that leads to a better understanding of its efficacy and to the proper selection of its design parameters.

Elif Vural, Pascal Frossard

We present a performance analysis for image registration with gradient descent methods. We consider a typical multiscale registration setting where the global 2-D translation between a pair of images is estimated by smoothing the images and minimizing the distance between them with gradient descent. Our study particularly concentrates on the effect of noise and low-pass filtering on the alignment accuracy. We adopt an analytic representation for images and analyze the well-behavedness of the image distance function by estimating the neighborhood of translations for which it is free of undesired local minima. This corresponds to the neighborhood of translation vectors that are correctly computable with a simple gradient descent minimization. We show that the area of this neighborhood increases at least quadratically with the smoothing filter size, which justifies the use of a smoothing step in image registration with local optimizers such as gradient descent. We then examine the effect of noise on the alignment accuracy and derive an upper bound for the alignment error in terms of the noise properties and filter size. Our main finding is that the error increases at a rate that is at least linear with respect to the filter size. Therefore, smoothing improves the well-behavedness of the distance function; however, this comes at the cost of amplifying the alignment error in noisy settings. Our results provide a mathematical insight about why hierarchical techniques are effective in image registration, suggesting that the multiscale coarse-to-fine alignment strategy of these techniques is very suitable from the perspective of the trade-off between the well-behavedness of the objective function and the registration accuracy. To the best of our knowledge, this is the first such study for descent-based image registration.