Transduction on Directed Graphs via Absorbing Random Walks.

In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality by means of symmetrization, we propose a novel random walk approach on directed graphs using absorbing Markov chains, which can be regarded as maximizing the accumulated expected number of visits from the unlabeled transient states. Our algorithm is simple, easy to implement, and works with large-scale graphs on binary, multiclass, and multi-label prediction problems. Moreover, it is capable of preserving the graph structure even when the input graph is sparse and changes over time, as well as retaining weak signals presented in the directed edges. We present its intimate connections to a number of existing methods, including graph kernels, graph Laplacian based methods, and spanning forest of graphs. Its computational complexity and the generalization error are also studied. Empirically, our algorithm is evaluated on a wide range of applications, where it has shown to perform competitively comparing to a suite of state-of-the-art methods. In particular, our algorithm is shown to work exceptionally well with large sparse directed graphs with e.g., millions of nodes and tens of millions of edges, where it significantly outperforms other state-of-the-art methods. In the dynamic graph setting involving insertion or deletion of nodes and edge-weight changes over time, it also allows efficient online updates that produce the same results as of the batch update counterparts.

NeuronCyto II: An automatic and quantitative solution for crossover neural cells in high throughput screening.

Microscopy is a fundamental technology driving new biological discoveries. Today microscopy allows a large number of images to be acquired using, for example, High Throughput Screening (HTS) and 4D imaging. It is essential to be able to interrogate these images and extract quantitative information in an automated fashion. In the context of neurobiology, it is important to automatically quantify the morphology of neurons in terms of neurite number, length, branching and complexity, etc. One major issue in quantification of neuronal morphology is the "crossover" problem where neurites cross and it is difficult to assign which neurite belongs to which cell body. In the present study, we provide a solution to the "crossover" problem, the software package NeuronCyto II. NeuronCyto II is an interactive and user-friendly software package for automatic neurite quantification. It has a well-designed graphical user interface (GUI) with only a few free parameters allowing users to optimize the software by themselves and extract relevant quantitative information routinely. Users are able to interact with the images and the numerical features through the Result Inspector. The processing of neurites without crossover was presented in our previous work. Our solution for the "crossover" problem is developed based on our recently published work with directed graph theory. Both methods are implemented in NeuronCyto II. The results show that our solution is able to significantly improve the reliability and accuracy of the neurons displaying "crossover." NeuronCyto II is freely available at the website: https://sites.google.com/site/neuroncyto/, which includes user support and where software upgrades will also be placed in the future. © 2016 The Authors. Cytometry Part A Published by Wiley Periodicals, Inc. on behalf of ISAC.

A Graph-Theoretical Approach for Tracing Filamentary Structures in Neuronal and Retinal Images.

The aim of this study is about tracing filamentary structures in both neuronal and retinal images. It is often crucial to identify single neurons in neuronal networks, or separate vessel tree structures in retinal blood vessel networks, in applications such as drug screening for neurological disorders or computer-aided diagnosis of diabetic retinopathy. Both tasks are challenging as the same bottleneck issue of filament crossovers is commonly encountered, which essentially hinders the ability of existing systems to conduct large-scale drug screening or practical clinical usage. To address the filament crossovers' problem, a two-step graph-theoretical approach is proposed in this paper. The first step focuses on segmenting filamentary pixels out of the background. This produces a filament segmentation map used as input for the second step, where they are further separated into disjointed filaments. Key to our approach is the idea that the problem can be reformulated as label propagation over directed graphs, such that the graph is to be partitioned into disjoint sub-graphs, or equivalently, each of the neurons (vessel trees) is separated from the rest of the neuronal (vessel) network. This enables us to make the interesting connection between the tracing problem and the digraph matrix-forest theorem in algebraic graph theory for the first time. Empirical experiments on neuronal and retinal image datasets demonstrate the superior performance of our approach over existing methods.

Tracing retinal blood vessels by matrix-forest theorem of directed graphs.

This paper aims to trace retinal blood vessel trees in fundus images. This task is far from being trivial as the crossover of vessels are commonly encountered in image-based vessel networks. Meanwhile it is often crucial to separate the vessel tree structures in applications such as diabetic retinopathy analysis. In this work, a novel directed graph based approach is proposed to cast the task as label propagation over directed graphs, such that the graph is to be partitioned into disjoint sub-graphs, or equivalently, each of the vessel trees is traced and separated from the rest of the vessel network. Then the tracing problem is addressed by making novel usage of the matrix-forest theorem in algebraic graph theory. Empirical experiments on synthetic as well as publicly available fundus image datasets demonstrate the applicability of our approach.

Tracing retinal vessel trees by transductive inference.

BACKGROUND: Structural study of retinal blood vessels provides an early indication of diseases such as diabetic retinopathy, glaucoma, and hypertensive retinopathy. These studies require accurate tracing of retinal vessel tree structure from fundus images in an automated manner. However, the existing work encounters great difficulties when dealing with the crossover issue commonly-seen in vessel networks. RESULTS: In this paper, we consider a novel graph-based approach to address this tracing with crossover problem: After initial steps of segmentation and skeleton extraction, its graph representation can be established, where each segment in the skeleton map becomes a node, and a direct contact between two adjacent segments is translated to an undirected edge of the two corresponding nodes. The segments in the skeleton map touching the optical disk area are considered as root nodes. This determines the number of trees to-be-found in the vessel network, which is always equal to the number of root nodes. Based on this undirected graph representation, the tracing problem is further connected to the well-studied transductive inference in machine learning, where the goal becomes that of properly propagating the tree labels from those known root nodes to the rest of the graph, such that the graph is partitioned into disjoint sub-graphs, or equivalently, each of the trees is traced and separated from the rest of the vessel network. This connection enables us to address the tracing problem by exploiting established development in transductive inference. Empirical experiments on public available fundus image datasets demonstrate the applicability of our approach. CONCLUSIONS: We provide a novel and systematic approach to trace retinal vessel trees with the present of crossovers by solving a transductive learning problem on induced undirected graphs.