In this paper we use the Birkhoff\char21{}von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power.
In this paper, we present a novel approach for aerial obstacle detection (e.g., branches or awnings) using a 3-D smartphone in the context of the visually impaired (VI) people assistance. This kind of obstacles are especially challenging because they cannot be detected by the walking stick or the guide dog. The algorithm captures the 3-D data of the scene through stereo vision. To our knowledge, this is the first work that presents a technology able to obtain real 3-D measures with smartphones in real time. The orientation sensors of the device (magnetometer and accelerometer) are used to approximate the walking direction of the user, in order to look for the obstacles only in such a direction. The obtained 3-D data are compressed and then linearized for detecting the potential obstacles. Potential obstacles are tracked in order to accumulate enough evidence to alert the user only when a real obstacle is found. In the experimental section, we show the results of the algorithm in several situations using real data and helped by VI users.
13 July 2022 in Engineering Applications of Artificial Intelligence
In this paper we cast the problem of graph matching as one of non-rigid manifold alignment. The low dimensional manifolds are from the commute time embedding and are matched though coherent point drift. Although there have been a number of attempts to realise graph matching in this way, in this paper we propose a novel information-theoretic measure of alignment, the so-called symmetrized normalized-entropy-square variation. We successfully test this dissimilarity measure between manifolds on a a challenging database. The measure is estimated by means of the bypass Leonenko entropy functional. In addition we prove that the proposed measure induces a positive definite kernel between the probability density functions associated with the manifolds and hence between graphs after deformation. In our experiments we find that the optimal embedding is associated to the commute time distance and we also find that our approach, which is purely topological, outperforms several state-of-the-art graph-based algorithms for point matching.