Shirakawa, Ryo, Yokoyama, Yusei, Okazaki, Fumiya, Takigawa, Ichigaku

Classification and regression in which the inputs are graphs of arbitrary size and shape have been paid attention in various fields such as computational chemistry and bioinformatics. Subgraph indicators are often used as the most fundamental features, but the number of possible subgraph patterns are intractably large due to the combinatorial explosion. We propose a novel efficient algorithm to jointly learn relevant subgraph patterns and nonlinear models of their indicators. Previous methods for such joint learning of subgraph features and models are based on search for single best subgraph features with specific pruning and boosting procedures of adding their indicators one by one, which result in linear models of subgraph indicators. In contrast, the proposed approach is based on directly learning regression trees for graph inputs using a newly derived bound of the total sum of squares for data partitions by a given subgraph feature, and thus can learn nonlinear models through standard gradient boosting. An illustrative example we call the Graph-XOR problem to consider nonlinearity, numerical experiments with real datasets, and scalability comparisons to naive approaches using explicit pattern enumeration are also presented.

Multi-robot path planning is difficult due to the combinatorial explosion of the search space with every new robot added. Complete search of the combined state-space soon becomes intractable. In this paper we present a novel form of abstraction that allows us to plan much more efficiently. The key to this abstraction is the partitioning of the map into subgraphs of known structure with entry and exit restrictions which we can represent compactly. Planning then becomes a search in the much smaller space of subgraph configurations. Once an abstract plan is found, it can be quickly resolved into a correct (but possibly sub-optimal) concrete plan without the need for further search. We prove that this technique is sound and complete and demonstrate its practical effectiveness on a real map. A contending solution, prioritised planning, is also evaluated and shown to have similar performance albeit at the cost of completeness. The two approaches are not necessarily conflicting; we demonstrate how they can be combined into a single algorithm which outperforms either approach alone.

Hoffmann, Ruth (University of Glasgow) | McCreesh, Ciaran (University of Glasgow) | Reilly, Craig (University of Glasgow)

When a small pattern graph does not occur inside a larger target graph, we can ask how to find "as much of the pattern as possible" inside the target graph. In general, this is known as the maximum common subgraph problem, which is much more computationally challenging in practice than subgraph isomorphism. We introduce a restricted alternative, where we ask if all but k vertices from the pattern can be found in the target graph. This allows for the development of slightly weakened forms of certain invariants from subgraph isomorphism which are based upon degree and number of paths. We show that when k is small, weakening the invariants still retains much of their effectiveness. We are then able to solve this problem on the standard problem instances used to benchmark subgraph isomorphism algorithms, despite these instances being too large for current maximum common subgraph algorithms to handle. Finally, by iteratively increasing k, we obtain an algorithm which is also competitive for the maximum common subgraph

Exponential Random Graphs Models (ERGM) are common, simple statistical models for social network and other network structures. Unfortunately, inference and learning with them is hard even for small networks because their partition functions are intractable for precise computation. In this paper, we introduce a new quadratic time deterministic approximation to these partition functions. Our main insight enabling this advance is that subgraph statistics is sufficient to derive a lower bound for partition functions given that the model is not dominated by a few graphs. The proposed method differs from existing methods in its ways of exploiting asymptotic properties of subgraph statistics. Compared to the current Monte Carlo simulation based methods, the new method is scalable, stable, and precise enough for inference tasks.

Jakubisin, Daniel J., Buehrer, R. Michael, da Silva, Claudio R. C. M.

Receiver algorithms which combine belief propagation (BP) with the mean field (MF) approximation are well-suited for inference of both continuous and discrete random variables. In wireless scenarios involving detection of multiple signals, the standard construction of the combined BP-MF framework includes the equalization or multi-user detection functions within the MF subgraph. In this paper, we show that the MF approximation is not particularly effective for multi-signal detection. We develop a new factor graph construction for application of the BP-MF framework to problems involving the detection of multiple signals. We then develop a low-complexity variant to the proposed construction in which Gaussian BP is applied to the equalization factors. In this case, the factor graph of the joint probability distribution is divided into three subgraphs: (i) a MF subgraph comprised of the observation factors and channel estimation, (ii) a Gaussian BP subgraph which is applied to multi-signal detection, and (iii) a discrete BP subgraph which is applied to demodulation and decoding. Expectation propagation is used to approximate discrete distributions with a Gaussian distribution and links the discrete BP and Gaussian BP subgraphs. The result is a probabilistic receiver architecture with strong theoretical justification which can be applied to multi-signal detection.