Graph-structured data, where nodes exhibit either pair-wise or high-order relations, are ubiquitous and essential in graph learning. Despite the great achievement made by existing graph learning models, these models use the direct information (edges or hyperedges) from graphs and do not adopt the underlying indirect information (hidden pair-wise or high-order relations). To address this issue, in this paper, we propose a general framework named Simplicial Complex Neural (SCN) network, in which we construct a simplicial complex based on the direct and indirect graph information from a graph so that all information can be employed in the complex network learning. Specifically, we learn representations of simplices by aggregating and integrating information from all the simplices together via layer-by-layer simplicial complex propagation. In consequence, the representations of nodes, edges, and other high-order simplices are obtained simultaneously and can be used for learning purposes. By making use of block matrix properties, we derive the theoretical bound of the simplicial complex filter learnt by the propagation and establish the generalization error bound of the proposed simplicial complex network. We perform extensive experiments on node (0-simplex), edge (1-simplex), and triangle (2-simplex) classifications, and promising results demonstrate the performance of the proposed method is better than that of existing graph and hypergraph network approaches.

The task of transfer learning using pretrained convolutional neural networks is considered. We propose a convolution-SVD layer to analyze the convolution operators with a singular value decomposition computed in the Fourier domain. Singular vectors extracted from the source domain are transferred to the target domain, whereas the singular values are fine-tuned with a target data set. In this way, dimension reduction is achieved to avoid overfitting, while some flexibility to fine-tune the convolution kernels is maintained. We extend an existing convolution kernel reconstruction algorithm to allow for a reconstruction from an arbitrary set of learned singular values. A generalization bound for a single convolution-SVD layer is devised to show the consistency between training and testing errors. We further introduce a notion of transfer learning gap. We prove that the testing error for a single convolution-SVD layer is bounded in terms of the gap, which motivates us to develop a regularization model with the gap as the regularizer. Numerical experiments are conducted to demonstrate the superiority of the proposed model in solving classification problems and the influence of various parameters. In particular, the regularization is shown to yield a significantly higher prediction accuracy.

Automatically annotating words for images is a key to semantic-level image retrieval. Recently, several embedding learning based methods achieve good performance in this task which inspires this paper. Here we propose a novel word embedding model in which both images and words can be represented in the same embedding space. The embedding space is learnt in a discriminative nearest neighbor manner such that the annotation information could be propagated among neighbors. In order to accelerate model learning and testing, approximate-nearest-neighbor search is performed, and word embedding space is learnt in a stochastic manner. The experimental results demonstrate the effectiveness of the proposed method.

The soft additive segmentation model attempts to solve the problem related to the segmentation of overlapping objects with additive intensity value. An issue in optimizing the soft additive segmentation functional is that a high-order nonlinear partial differential equation needs to be solved, which, for most standard algorithms, involves high computational cost. In this paper, we propose a fast and efficient numerical algorithm to optimize the soft additive segmentation model. We reformulate the original minimization problem into a sequence of simpler minimization problems that can be solved efficiently by using the augmented Lagrangian method. Numerical tests on real and synthetic cases are presented to demonstrate the efficiency of our algorithm.

In this paper, we consider the problem of segmentation of large collections of images. We propose a semisupervised optimization model that determines an efficient segmentation of many input images. The advantages of the model are twofold. First, the segmentation is highly controllable by the user so that the user can easily specify what he/she wants. This is done by allowing the user to provide, either offline or interactively, some (fully or partially) labeled pixels in images as strong priors for the model. Second, the model requires only minimal tuning of model parameters during the initial stage. Once initial tuning is done, the setup can be used to automatically segment a large collection of images that are distinct but share similar features. We will show the mathematical properties of the model such as existence and uniqueness of solution and establish a maximum/minimum principle for the solution of the model. Extensive experiments on various collections of biological images suggest that the proposed model is effective for segmentation and is computationally efficient.

Loss of information in a wavelet domain can occur during storage or transmission when the images are formatted and stored in terms of wavelet coefficients. This calls for image inpainting in wavelet domains. In this paper, a variational approach is used to formulate the reconstruction problem. We propose a simple but very efficient iterative scheme to calculate an optimal solution and prove its convergence. Numerical results are presented to show the performance of the proposed algorithm.

We propose a variant of the Mumford-Shah model for the segmentation of a pair of overlapping objects with additive intensity value. Unlike standard segmentation models, it does not only determine distinct objects in the image, but also recover the possibly multiple membership of the pixels. To accomplish this, some a priori knowledge about the smoothness of the object boundary is integrated into the model. Additivity is imposed through a soft constraint which allows the user to control the degree of additivity and is more robust than the hard constraint. We also show analytically that the additivity parameter can be chosen to achieve some stability conditions. To solve the optimization problem involving geometric quantities efficiently, we apply a multiphase level set method. Segmentation results on synthetic and real images validate the good performance of our model, and demonstrate the model's applicability to images with multiple channels and multiple objects.

A wavelet inpainting problem refers to the problem of filling in missing wavelet coefficients in an image. A variational approach was used by Chan et al. The resulting functional was minimized by the gradient descent method. In this paper, we use an optimization transfer technique which involves replacing their univariate functional by a bivariate functional by adding an auxiliary variable. Our bivariate functional can be minimized easily by alternating minimization: for the auxiliary variable, the minimum has a closed form solution, and for the original variable, the minimization problem can be formulated as a classical total variation (TV) denoising problem and, hence, can be solved efficiently using a dual formulation. We show that our bivariate functional is equivalent to the original univariate functional. We also show that our alternating minimization is convergent. Numerical results show that the proposed algorithm is very efficient and outperforms that of Chan et al.

The Mumford-Shah model is one of the most successful image segmentation models. However, existing algorithms for the model are often very sensitive to the choice of the initial guess. To make use of the model effectively, it is essential to develop an algorithm which can compute a global or near global optimal solution efficiently. While gradient descent based methods are well-known to find a local minimum only, even many stochastic methods do not provide a practical solution to this problem either. In this paper, we consider the computation of a global minimum of the multiphase piecewise constant Mumford-Shah model. We propose a hybrid approach which combines gradient based and stochastic optimization methods to resolve the problem of sensitivity to the initial guess. At the heart of our algorithm is a well-designed basin hopping scheme which uses global updates to escape from local traps in a way that is much more effective than standard stochastic methods. In our experiments, a very high-quality solution is obtained within a few stochastic hops whereas the solutions obtained with simulated annealing are incomparable even after thousands of steps. We also propose a multiresolution approach to reduce the computational cost and enhance the search for a global minimum. Furthermore, we derived a simple but useful theoretical result relating solutions at different spatial resolutions.

In this paper, we describe a 2-pass iterative scheme to solve the general partial differential equation (PDE) related to the Shape-from-Shading (SFS) problem under both distant and close point light sources. In particular, we discuss its applications in restoring warped document images that often appear in the daily snapshots. The proposed method consists of two steps. First the image irradiance equation is formulated as a static Hamilton-Jacobi (HJ) equation and solved using a fast sweeping strategy with Lax-Friedrichs Hamiltonian. However, abrupt errors may arise when applying to real document images due to noises in the approximated shading image. To reduce the noise sensitivity, a minimization method thus follows to smooth out the abrupt ridges in the initial result and produce a better reconstruction. Experiments on synthetic surfaces show promising results comparing to the ground truth data. Moreover, a general framework is developed, which demonstrates that the SFS method can help to remove both geometric and photometric distortions in warped document images for better visual appearance and higher recognition rate.

This paper presents a restoration framework for correcting both photometric and geometric distortions in camera-based images of non-planar shaped documents to facilitate human perception and machine recognition. The photometric distortions, usually perceived as shading artifacts, are corrected by separating the shading image from the reflectance image through digital inpainting and surface fitting techniques. Meanwhile, the extracted shading image is also used to recover the document's surface shape through a Shape-from-Shading (SFS) method with a generic formulation of the image irradiance under arbitrary illumination conditions. The recovered surface shape is then employed to correct the geometric distortions through a physically-based flattening process. Results on real document images demonstrate the performance of each sub-task and the functionality of the whole framework. OCR results on restored images also show great improvements over the original distorted images.

Shading distortions are often perceived in geometrically distorted document images due to the change of surface normal with respect to the illumination direction. Such distortions are undesirable because they hamper OCR performance tremendously even when the geometric distortions are corrected. In this paper, we propose an effective method that removes shading distortions in images of documents with various geometric shapes based on the notion of intrinsic images. We first try to derive the shading image using an inpainting technique with an automatic mask generation routine and then apply a surface fitting procedure with radial basis functions to remove pepper noises in the inpainted image and return a smooth shading image. Once the shading image is extracted, the reflectance image can be obtained automatically. Experiments on a wide range of distorted document images demonstrate a robust performance. Moreover, we also show its potential applications to the restoration of historical handwritten documents.

BACKGROUND: Network methods are increasingly used to represent the interactions of genes and/or proteins. Genes or proteins that are directly linked may have a similar biological function or may be part of the same biological pathway. Since the information on the connection (adjacency) between 2 nodes may be noisy or incomplete, it can be desirable to consider alternative measures of pairwise interconnectedness. Here we study a class of measures that are proportional to the number of neighbors that a pair of nodes share in common. For example, the topological overlap measure by Ravasz et al. 1 can be interpreted as a measure of agreement between the m = 1 step neighborhoods of 2 nodes. Several studies have shown that two proteins having a higher topological overlap are more likely to belong to the same functional class than proteins having a lower topological overlap. Here we address the question whether a measure of topological overlap based on higher-order neighborhoods could give rise to a more robust and sensitive measure of interconnectedness. RESULTS: We generalize the topological overlap measure from m = 1 step neighborhoods to m > or = 2 step neighborhoods. This allows us to define the m-th order generalized topological overlap measure (GTOM) by (i) counting the number of m-step neighbors that a pair of nodes share and (ii) normalizing it to take a value between 0 and 1. Using theoretical arguments, a yeast co-expression network application, and a fly protein network application, we illustrate the usefulness of the proposed measure for module detection and gene neighborhood analysis. CONCLUSION: Topological overlap can serve as an important filter to counter the effects of spurious or missing connections between network nodes. The m-th order topological overlap measure allows one to trade-off sensitivity versus specificity when it comes to defining pairwise interconnectedness and network modules.

We propose and study the notion of dense regions for the analysis of categorized gene expression data and present some searching algorithms for discovering them. The algorithms can be applied to any categorical data matrices derived from gene expression level matrices. We demonstrate that dense regions are simple but useful and statistically significant patterns that can be used to 1) identify genes and/or samples of interest and 2) eliminate genes and/or samples corresponding to outliers, noise, or abnormalities. Some theoretical studies on the properties of the dense regions are presented which allow us to characterize dense regions into several classes and to derive tailor-made algorithms for different classes of regions. Moreover, an empirical simulation study on the distribution of the size of dense regions is carried out which is then used to assess the significance of dense regions and to derive effective pruning methods to speed up the searching algorithms. Real microarray data sets are employed to test our methods. Comparisons with six other well-known clustering algorithms using synthetic and real data are also conducted which confirm the superiority of our methods in discovering dense regions. The DRIFT code and a tutorial are available as supplemental material, which can be found on the Computer Society Digital Library at http://computer.org/tcbb/archives.htm.

This paper studies image deblurring problems using a total variation-based model, with a non-negativity constraint. The addition of the non-negativity constraint improves the quality of the solutions, but makes the solution process a difficult one. The contribution of our work is a fast and robust numerical algorithm to solve the non-negatively constrained problem. To overcome the nondifferentiability of the total variation norm, we formulate the constrained deblurring problem as a primal-dual program which is a variant of the formulation proposed by Chan, Golub, and Mulet for unconstrained problems. Here, dual refers to a combination of the Lagrangian and Fenchel duals. To solve the constrained primal-dual program, we use a semi-smooth Newton's method. We exploit the relationship between the semi-smooth Newton's method and the primal-dual active set method to achieve considerable simplification of the computations. The main advantages of our proposed scheme are: no parameters need significant adjustment, a standard inverse preconditioner works very well, quadratic rate of local convergence (theoretical and numerical), numerical evidence of global convergence, and high accuracy of solving the optimality system. The scheme shows robustness of performance over a wide range of parameters. A comprehensive set of numerical comparisons are provided against other methods to solve the same problem which show the speed and accuracy advantages of our scheme.

Density-based clustering has the advantages for 1) allowing arbitrary shape of cluster and 2) not requiring the number of clusters as input. However, when clusters touch each other, both the cluster centers and cluster boundaries (as the peaks and valleys of the density distribution) become fuzzy and difficult to determine. We introduce the notion of cluster intensity function (CIF) which captures the important characteristics of clusters. When clusters are well-separated, CIFs are similar to density functions. But, when clusters become closed to each other, CIFs still clearly reveal cluster centers, cluster boundaries, and degree of membership of each data point to the cluster that it belongs. Clustering through bump hunting and valley seeking based on these functions are more robust than that based on density functions obtained by kernel density estimation, which are often oscillatory or oversmoothed. These problems of kernel density estimation are resolved using Level Set Methods and related techniques. Comparisons with two existing density-based methods, valley seeking and DBSCAN, are presented which illustrate the advantages of our approach.