This paper proposes a novel framework for modelling the spread of financial crises in complex networks, combining financial data, Extreme Value Theory and an epidemiological transmission model. We accommodate two key aspects of contagion modelling: fundamentals-based contagion, where the transmission is due to direct financial linkages, and pure contagion, where a crisis might trigger additional crises due to global effects. We use stock price, geographical location and economic sector data for a set of 398 companies to construct multiplex networks of four layers, on which a susceptible-infected-recovered transmission model is defined, in order to model the spread of financial shocks between companies by accounting for their interconnected nature. By utilizing stock price data for the 2008 and 2020 financial crises, we investigate and assess the effectiveness of our model in forecasting the propagation of financial shocks through the network, where a shock is detected by measuring stock price volatility. The results suggest that the proposed framework is effective in predicting the spread of financial crises. Our findings demonstrate the significance of each layer of the multiplex network structure, which differentiates between various transmission pathways, for predicting the number of affected companies, as well as for company-, sector- or location-specific predictions.

@en

In network science, one of the significant and challenging subjects is the detection of communities. Modularity [1] is a measure of community structure that compares connectivity in the network with the expected connectivity in a graph sampled from a random null model. Its optimisation is a common approach to tackle the community detection problem. We present a new method for modularity maximisation, which is based on the observation that modularity can be expressed in terms of total variation on the graph and signless total variation on the null model. The resulting algorithm is of Merriman–Bence–Osher (MBO) type. Different from earlier methods of this type, the new method can easily accommodate different choices of the null model. Besides theoretical investigations of the method, we include in this paper numerical comparisons with other community detection methods, among which the MBO-type methods of Hu et al. [2] and Boyd et al. [3], and the Leiden algorithm [4].

@en

The original article has been updated to correct some missing reference citations in the text.

@en

Neural networks have been very successful in many applications; we often, however, lack a theoretical understanding of what the neural networks are actually learning. This problem emerges when trying to generalise to new data sets. The contribution of this paper is to show that, for the residual neural network model, the deep layer limit coincides with a parameter estimation problem for a nonlinear ordinary differential equation. In particular, whilst it is known that the residual neural network model is a discretisation of an ordinary differential equation, we show convergence in a variational sense. This implies that optimal parameters converge in the deep layer limit. This is a stronger statement than saying for a fixed parameter the residual neural network model converges (the latter does not in general imply the former). Our variational analysis provides a discrete-to-continuum Γ -convergence result for the objective function of the residual neural network training step to a variational problem constrained by a system of ordinary differential equations; this rigorously connects the discrete setting to a continuum problem.

@en

Practical image segmentation tasks concern images which must be reconstructed from noisy, distorted, and/or incomplete observations. A recent approach for solving such tasks is to perform this reconstruction jointly with the segmentation, using each to guide the other. However, this work has so far employed relatively simple segmentation methods, such as the Chan--Vese algorithm. In this paper, we present a method for joint reconstruction-segmentation using graph-based segmentation methods, which have been seeing increasing recent interest. Complications arise due to the large size of the matrices involved, and we show how these complications can be managed. We then analyze the convergence properties of our scheme. Finally, we apply this scheme to distorted versions of ``two cows"" images familiar from previous graph-based segmentation literature, first to a highly noised version and second to a blurred version, achieving highly accurate segmentations in both cases. We compare these results to those obtained by sequential reconstruction-segmentation approaches, finding that our method competes with, or even outperforms, those approaches in terms of reconstruction and segmentation accuracy.

@en

This paper introduces a semi-discrete implicit Euler (SDIE) scheme for the Allen-Cahn equation (ACE) with fidelity forcing on graphs. The continuous-in-time version of this differential equation was pioneered by Bertozzi and Flenner in 2012 as a method for graph classification problems, such as semi-supervised learning and image segmentation. In 2013, Merkurjev et. al. used a Merriman-Bence-Osher (MBO) scheme with fidelity forcing instead, as heuristically it was expected to give similar results to the ACE. The current paper rigorously establishes the graph MBO scheme with fidelity forcing as a special case of an SDIE scheme for the graph ACE with fidelity forcing. This connection requires the use of the double-obstacle potential in the ACE, as was already demonstrated by Budd and Van Gennip in 2020 in the context of ACE without a fidelity forcing term. We also prove that solutions of the SDIE scheme converge to solutions of the graph ACE with fidelity forcing as the discrete time step converges to zero. In the second part of the paper we develop the SDIE scheme as a classification algorithm. We also introduce some innovations into the algorithms for the SDIE and MBO schemes. For large graphs, we use a QR decomposition method to compute an eigendecomposition from a Nyström extension, which outperforms the method used by, for example, Bertozzi and Flenner in 2012, in accuracy, stability, and speed. Moreover, we replace the Euler discretization for the scheme's diffusion step by a computation based on the Strang formula for matrix exponentials. We apply this algorithm to a number of image segmentation problems, and compare the performance with that of the graph MBO scheme with fidelity forcing. We find that while the general SDIE scheme does not perform better than the MBO special case at this task, our other innovations lead to a significantly better segmentation than that from previous literature. We also empirically quantify the uncertainty that this segmentation inherits from the randomness in the Nyström extension.

@en

An emerging technique in image segmentation, semi-supervised learning and general classification problems concerns the use of phase-separating flows defined on finite graphs. This technique was pioneered in Bertozzi and Flenner (2012, Multiscale Modeling and Simulation 10(3), 1090-1118), which used the Allen-Cahn flow on a graph, and was then extended in Merkurjev et al. (2013, SIAM J. Imaging Sci. 6(4), 1903-1930) using instead the Merriman-Bence-Osher (MBO) scheme on a graph. In previous work by the authors, Budd and Van Gennip (2020, SIAM J. Math. Anal. 52(5), 4101-4139), we gave a theoretical justification for this use of the MBO scheme in place of Allen-Cahn flow, showing that the MBO scheme is a special case of a 'semi-discrete' numerical scheme for Allen-Cahn flow. In this paper, we extend this earlier work, showing that this link via the semi-discrete scheme is robust to passing to the mass-conserving case. Inspired by Rubinstein and Sternberg (1992, IMA J. Appl. Math. 48, 249-264), we define a mass-conserving Allen-Cahn equation on a graph. Then, with the help of the tools of convex optimisation, we show that our earlier machinery can be applied to derive the mass-conserving MBO scheme on a graph as a special case of a semi-discrete scheme for mass-conserving Allen-Cahn. We give a theoretical analysis of this flow and scheme, proving various desired properties like existence and uniqueness of the flow and convergence of the scheme, and also show that the semi-discrete scheme yields a choice function for solutions to the mass-conserving MBO scheme.

@en

We introduce a principled method for the signed clustering problem, where the goal is to partition a weighted undirected graph whose edge weights take both positive and negative values, such that edges within the same cluster are mostly positive, while edges spanning across clusters are mostly negative. Our method relies on a graph-based diffuse interface model formulation utilizing the Ginzburg-Landau functional, based on an adaptation of the classic numerical Merriman-Bence-Osher (MBO) scheme for minimizing such graph-based functionals. The proposed object ive function aims to minimize the total weight of inter-cluster positively-weighted edges, while maximizing the total weight of the inter-cluster negatively-weighted edges. Our method scales to large sparse networks, and can be easily adjusted to incorporate labelled data information, as is often the case in the context of semisupervised learning. We tested our method on a number of both synthetic stochastic block models and real-world data sets (including financial correlation matrices), and obtained promising results that compare favourably against a number of state-of-the-art approaches from the recent literature.

@en

In recent years there has been an emerging interest in PDE-like flows defined on finite graphs, with applications in clustering and image segmentation. In particular for image segmentation and semisupervised learning Bertozzi and Flenner [Multiscale Model. Simul., 10 (2012), pp. 1090--1118] developed an algorithm based on the Allen--Cahn (AC) gradient flow of a graph Ginzburg--Landau functional, and Merkurjev, Kostić, and Bertozzi [SIAM J. Imaging Sci., 6 (2013), pp. 1903--1930] devised a variant algorithm based instead on graph Merriman--Bence--Osher (MBO) dynamics. This work offers rigorous justification for this use of the MBO scheme in place of AC flow. First, we choose the double-obstacle potential for the Ginzburg--Landau functional and derive well-posedness and regularity results for the resulting graph AC flow. Next, we exhibit a “semidiscrete” time-discretization scheme for AC flow of which the MBO scheme is a special case. We investigate the long-time behavior of this scheme and prove its convergence to the AC trajectory as the time-step vanishes. Finally, following a question raised by Van Gennip, Guillen, Osting, and Bertozzi [Milan J. Math., 82 (2014), pp. 3--65], we exhibit results toward proving a link between double-obstacle AC flow and mean curvature flow on graphs. We show some promising $\Gamma$-convergence results and translate to the graph setting two comparison principles used by Chen and Elliott [Proc. Math. Phys. Sci., 444 (1994), pp. 429--445] to prove the analogous link in the continuum.


Read More: https://epubs.siam.org/doi/10.1137/19M1277394@en

The Max-Cut problem is a well known combinatorial optimization problem. In this paper we describe a fast approximation method. Given a graph G, we want to find a cut whose size is maximal among all possible cuts. A cut is a partition of the vertex set of G into two disjoint subsets. For an unweighted graph, the size of the cut is the number of edges that have one vertex on either side of the partition; we also consider a weighted version of the problem where each edge contributes a nonnegative weight to the cut. We introduce the signless Ginzburg–Landau functional and prove that this functional Γ-converges to a Max-Cut objective functional. We approximately minimize this functional using a graph based signless Merriman–Bence–Osher (MBO) scheme, which uses a signless Laplacian. We derive a Lyapunov functional for the iterations of our signless MBO scheme. We show experimentally that on some classes of graphs the resulting algorithm produces more accurate maximum cut approximations than the current state-of-the-art approximation algorithm. One of our methods of minimizing the functional results in an algorithm with a time complexity of O(|E|), where |E| is the total number of edges on G.

@en

This paper arose from a minisymposium held in 2018 at the 9th International Conference on Curves and Surface in Arcachon, France, and organized by Simon Masnou and Carola-Bibiane Schönlieb. This minisymposium featured a variety of recent developments of geometric partial differential equations and variational models which are directly or indirectly related to several problems in image and data processing. The current paper gathers three contributions which are in connection with the talks of three minisymposium speakers: Blanche Buet, Jean-Marie Mirebeau, and Yves van Gennip. The first contribution (Section 1) by Yves van Gennip provides a short overview of recent activity in the field of PDEs on graphs, without aiming to be exhaustive. The main focus is on techniques related to the graph Ginzburg–Landau variational model, but some other research in the field is also mentioned at the end of the section. The second contribution (Section 2), written by Jean-Marie Mirebeau, François Desquilbet, Johann Dreo, and Frédéric Barbaresco presents a recent numerical method devoted to computing curves that globally minimize an energy featuring both a data driven term, and a second order curvature penalizing term. Applications to image segmentation are discussed, and recent progress on radar network configuration, in which the optimal curves represent an opponent’s trajectories, is described in detail. Lastly, Section 3 is devoted to a work by Blanche Buet, Gian Paolo Leonardi, and Simon Masnou on the definition and the approximation of weak curvatures for a large class of generalized surfaces, and in particular for point clouds, based on the geometric measure theoretic notion of varifolds. @en

The graph Merriman–Bence–Osher scheme produces, starting from an initial node subset, a sequence of node sets obtained by iteratively applying graph diffusion and thresholding to the characteristic (or indicator) function of the node subsets. One result in [14] gives sufficient conditions on the diffusion time to ensure that the set membership of a given node changes in one iteration of the scheme. In particular, these conditions only depend on local information at the node (information about neighbors and neighbors of neighbors of the node in question). In this paper we show that there does not exist any graph which satisfies these conditions. To make up for this negative result, this paper also presents positive results regarding the Merriman–Bence–Osher dynamics on star graphs and regular trees. In particular, we present sufficient (and in some cases necessary) results for the set membership of a given node to change in one iteration.

@en

In [BF12, BF16] the graph Ginzburg–Landau functional was introduced. Here u is a real-valued function on the node set V of a simple1, undirected graph (with ui its value at node i), ωij ≥ 0 are edge weights which are assumed to be positive on all edges in the graph and zero between non-neighbouring nodes i and j, ε is a positive parameter, and W is a double well potential with wells of equal depth. A typical choice is the quartic polynomial W(x) = x2(x − 1)2 which has wells of depth 0 at x = 0 and x = 1, but we will encounter some situations where other choices are useful or even necessary. @en