Search

We formulate an XAI-based model improvement approach for Graph Neural Networks (GNNs) for node classification, called Explanation Enhanced Graph Learning (EEGL). The goal is to improve predictive performance of GNN using explanations. EEGL is an iterative self-improving algorithm, which starts with a learned "vanilla" GNN, and repeatedly uses frequent subgraph mining to find relevant patterns in explanation subgraphs. These patterns are then filtered further to obtain application-dependent features corresponding to the presence of certain subgraphs in the node neighborhoods. Giving an application-dependent algorithm for such a subgraph-based extension of the Weisfeiler-Leman (1-WL) algorithm has previously been posed as an open problem. We present experimental evidence, with synthetic and real-world data, which show that EEGL outperforms related approaches in predictive performance and that it has a node-distinguishing power beyond that of vanilla GNNs. We also analyze EEGL's training dynamics.

We present a divergence-free and $H(div)$-conforming hybridized discontinuous Galerkin (HDG) method and a computationally efficient variant called embedded-HDG (E-HDG) for solving stationary incompressible viso-resistive magnetohydrodynamic (MHD) equations. The proposed E-HDG approach uses continuous facet unknowns for the vector-valued solutions (velocity and magnetic fields) while it uses discontinuous facet unknowns for the scalar variable (pressure and magnetic pressure). This choice of function spaces makes E-HDG computationally far more advantageous, due to the much smaller number of degrees of freedom, compared to the HDG counterpart. The benefit is even more significant for three-dimensional/high-order/fine mesh scenarios. On simplicial meshes, the proposed methods with a specific choice of approximation spaces are well-posed for linear(ized) MHD equations. For nonlinear MHD problems, we present a simple approach exploiting the proposed linear discretizations by using a Picard iteration. The beauty of this approach is that the divergence-free and $H(div)$-conforming properties of the velocity and magnetic fields are automatically carried over for nonlinear MHD equations. We study the accuracy and convergence of our E-HDG method for both linear and nonlinear MHD cases through various numerical experiments, including two- and three-dimensional problems with smooth and singular solutions. The numerical examples show that the proposed methods are pressure robust, and the divergence of the resulting velocity and magnetic fields is machine zero for both smooth and singular problems.

Motivated by the increasing interest in applications of graph geodesic convexity in machine learning and data mining, we present a heuristic for computing the geodesic convex hull of node sets in networks. It generates a set of almost maximal outerplanar spanning subgraphs for the input graph, computes the geodesic closure in each of these graphs, and regards a node as an element of the convex hull if it belongs to the closed sets for at least a user specified number of outerplanar graphs. Our heuristic algorithm runs in time linear in the number of edges of the input graph, i.e., it is faster with one order of magnitude than the standard algorithm computing the closure exactly. Its performance is evaluated empirically by approximating convexity based core-periphery decomposition of networks. Our experimental results with large real-world networks show that for most networks, the proposed heuristic was able to produce close approximations significantly faster than the standard algorithm computing the exact convex hulls. For example, while our algorithm calculated an approximate core-periphery decomposition in 5 hours or less for networks with more than 20 million edges, the standard algorithm did not terminate within 50 days.

In (J. Comput. Phys., 417, 109577, 2020) we introduced a space-time embedded-hybridizable discontinuous Galerkin method for the solution of the incompressible Navier-Stokes equations on time-dependent domains of which the motion of the domain is prescribed. This discretization is exactly mass conserving, locally momentum conserving, and energy-stable. In this manuscript we extend this discretization to fluid-rigid body interaction problems in which the motion of the fluid domain is not known a priori. To account for large rotational motion of the rigid body, we present a novel conforming space-time sliding mesh technique. We demonstrate the performance of the discretization on various numerical examples.

One of the central problems studied in the theory of machine learning is the question of whether, for a given class of hypotheses, it is possible to efficiently find a {consistent} hypothesis, i.e., which has zero training error. While problems involving {\em convex} hypotheses have been extensively studied, the question of whether efficient learning is possible for non-convex hypotheses composed of possibly several disconnected regions is still less understood. Although it has been shown quite a while ago that efficient learning of weakly convex hypotheses, a parameterized relaxation of convex hypotheses, is possible for the special case of Boolean functions, the question of whether this idea can be developed into a generic paradigm has not been studied yet. In this paper, we provide a positive answer and show that the consistent hypothesis finding problem can indeed be solved in polynomial time for a broad class of weakly convex hypotheses over metric spaces. To this end, we propose a general domain-independent algorithm for finding consistent weakly convex hypotheses and prove sufficient conditions for its efficiency that characterize the corresponding hypothesis classes. To illustrate our general algorithm and its properties, we discuss several non-trivial learning examples to demonstrate how it can be used to efficiently solve the corresponding consistent hypothesis finding problem. Without the weak convexity constraint, these problems are known to be computationally intractable. We then proceed to show that the general idea of our algorithm can even be extended to the case of extensional weakly convex hypotheses, as it naturally arise, e.g., when performing vertex classification in graphs. We prove that using our extended algorithm, the problem can be solved in polynomial time provided the distances in the domain can be computed efficiently., Comment: completely revised version, currently under review

We introduce and analyze a space-time hybridized discontinuous Galerkin method for the evolutionary Navier--Stokes equations. Key features of the numerical scheme include point-wise mass conservation, energy stability, and pressure robustness. We prove that there exists a solution to the resulting nonlinear algebraic system in two and three spatial dimensions, and that this solution is unique in two spatial dimensions under a small data assumption. A priori error estimates are derived for the velocity in a mesh-dependent energy norm.

The Weisfeiler-Lehman graph kernels are among the most prevalent graph kernels due to their remarkable time complexity and predictive performance. Their key concept is based on an implicit comparison of neighborhood representing trees with respect to equality (i.e., isomorphism). This binary valued comparison is, however, arguably too rigid for defining suitable similarity measures over graphs. To overcome this limitation, we propose a generalization of Weisfeiler-Lehman graph kernels which takes into account the similarity between trees rather than equality. We achieve this using a specifically fitted variation of the well-known tree edit distance which can efficiently be calculated. We empirically show that our approach significantly outperforms state-of-the-art methods in terms of predictive performance on datasets containing structurally more complex graphs beyond the typically considered molecular graphs., Comment: n/a

Several concept learning problems can be regarded as special cases of half-space separation in abstract closure systems over finite ground sets. For the typical scenario that the closure system is implicitly given via a closure operator, we show that the half-space separation problem is NP-complete. As a first approach to overcome this negative result, we relax the problem to maximal closed set separation, give a generic greedy algorithm solving this problem with a linear number of closure operator calls, and show that this bound is sharp. For a second direction, we consider Kakutani closure systems and prove that they are algorithmically characterized by the greedy algorithm. As a first special case of the general problem setting, we consider Kakutani closure systems over graphs and give a sufficient condition for this kind of closure systems in terms of forbidden graph minors. For a second special case, we then focus on closure systems over finite lattices, give an improved adaptation of the generic greedy algorithm, and present an application concerning subsumption lattices., Comment: An early version of this paper was presented at ECML/PKDD 2019 and has appeared in the Lecture Notes in Computer Science, Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2019

This paper presents a space-time embedded-hybridized discontinuous Galerkin (EHDG) method for the Navier--Stokes equations on moving domains. This method uses a different hybridization compared to the space-time hybridized discontinuous Galerkin (HDG) method we presented previously in (Int. J. Numer. Meth. Fluids 89: 519--532, 2019). In the space-time EHDG method the velocity trace unknown is continuous while the pressure trace unknown is discontinuous across facets. In the space-time HDG method, all trace unknowns are discontinuous across facets. Alternatively, we present also a space-time embedded discontinuous Galerkin (EDG) method in which all trace unknowns are continuous across facets. The advantage of continuous trace unknowns is that the formulation has fewer global degrees-of-freedom for a given mesh than when using discontinuous trace unknowns. Nevertheless, the discrete velocity field obtained by the space-time EHDG and EDG methods, like the space-time HDG method, is exactly divergence-free, even on moving domains. However, only the space-time EHDG and HDG methods result in divergence-conforming velocity fields. An immediate consequence of this is that the space-time EHDG and HDG discretizations of the conservative form of the Navier--Stokes equations are energy stable. The space-time EDG method, on the other hand, requires a skew-symmetric formulation of the momentum advection term to be energy-stable. Numerical examples will demonstrate the differences in solution obtained by the space-time EHDG, EDG, and HDG methods.

This paper presents the first analysis of a space--time hybridizable discontinuous Galerkin method for the advection--diffusion problem on time-dependent domains. The analysis is based on non-standard local trace and inverse inequalities that are anisotropic in the spatial and time steps. We prove well-posedness of the discrete problem and provide a priori error estimates in a mesh-dependent norm. Convergence theory is validated by a numerical example solving the advection--diffusion problem on a time-dependent domain for approximations of various polynomial degree.

We present a finite element method for the incompressible Navier--Stokes problem that is locally conservative, energy-stable and pressure-robust on time-dependent domains. To achieve this, the space--time formulation of the Navier--Stokes problem is considered. The space--time domain is partitioned into space--time slabs which in turn are partitioned into space--time simplices. A combined discontinuous Galerkin method across space--time slabs, and space--time hybridized discontinuous Galerkin method within a space--time slab, results in an approximate velocity field that is $H({\rm div})$-conforming and exactly divergence-free, even on time-dependent domains. Numerical examples demonstrate the convergence properties and performance of the method.

Neural spikes in the brain form stochastic sequences, i.e., belong to the class of pulse noises. This stochasticity is a counterintuitive feature because extracting information - such as the commonly supposed neural information of mean spike frequency - requires long times for reasonably low error probability. The mystery could be solved by noise-based logic, wherein randomness has an important function and allows large speed enhancements for special-purpose tasks, and the same mechanism is at work for the brain logic version of this concept., Comment: paper in press

Noise-based logic is a practically deterministic logic scheme inspired by the randomness of neural spikes and uses a system of uncorrelated stochastic processes and their superposition to represent the logic state. We briefly discuss various questions such as (i) What does practical determinism mean? (ii) Is noise-based logic a Turing machine? (iii) Is there hope to beat (the dreams of) quantum computation by a classical physical noise-based processor, and what are the minimum hardware requirements for that? Finally, (iv) we address the problem of random number generators and show that the common belief that quantum number generators are superior to classical (thermal) noise-based generators is nothing but a myth., Comment: paper in press