Review

A comprehensive review of graph convolutional networks: approaches and applications

  • Received: 03 October 2022 Revised: 04 March 2023 Accepted: 28 March 2023 Published: 31 May 2023
  • Convolutional neural networks (CNNs) utilize local translation invariance in the Euclidean domain and have remarkable achievements in computer vision tasks. However, there are many data types with non-Euclidean structures, such as social networks, chemical molecules, knowledge graphs, etc., which are crucial to real-world applications. The graph convolutional neural network (GCN), as a derivative of CNNs for non-Euclidean data, was established for non-Euclidean graph data. In this paper, we mainly survey the progress of GCNs and introduce in detail several basic models based on GCNs. First, we review the challenges in building GCNs, including large-scale graph data, directed graphs and multi-scale graph tasks. Also, we briefly discuss some applications of GCNs, including computer vision, transportation networks and other fields. Furthermore, we point out some open issues and highlight some future research trends for GCNs.

    Citation: Xinzheng Xu, Xiaoyang Zhao, Meng Wei, Zhongnian Li. A comprehensive review of graph convolutional networks: approaches and applications[J]. Electronic Research Archive, 2023, 31(7): 4185-4215. doi: 10.3934/era.2023213

    Related Papers:

    [1] Ye Sun, Daniel B. Work . Error bounds for Kalman filters on traffic networks. Networks and Heterogeneous Media, 2018, 13(2): 261-295. doi: 10.3934/nhm.2018012
    [2] Caterina Balzotti, Maya Briani, Benedetto Piccoli . Emissions minimization on road networks via Generic Second Order Models. Networks and Heterogeneous Media, 2023, 18(2): 694-722. doi: 10.3934/nhm.2023030
    [3] Matthieu Canaud, Lyudmila Mihaylova, Jacques Sau, Nour-Eddin El Faouzi . Probability hypothesis density filtering for real-time traffic state estimation and prediction. Networks and Heterogeneous Media, 2013, 8(3): 825-842. doi: 10.3934/nhm.2013.8.825
    [4] Maya Briani, Emiliano Cristiani . An easy-to-use algorithm for simulating traffic flow on networks: Theoretical study. Networks and Heterogeneous Media, 2014, 9(3): 519-552. doi: 10.3934/nhm.2014.9.519
    [5] Emiliano Cristiani, Smita Sahu . On the micro-to-macro limit for first-order traffic flow models on networks. Networks and Heterogeneous Media, 2016, 11(3): 395-413. doi: 10.3934/nhm.2016002
    [6] Samitha Samaranayake, Axel Parmentier, Ethan Xuan, Alexandre Bayen . A mathematical framework for delay analysis in single source networks. Networks and Heterogeneous Media, 2017, 12(1): 113-145. doi: 10.3934/nhm.2017005
    [7] Mauro Garavello, Benedetto Piccoli . On fluido-dynamic models for urban traffic. Networks and Heterogeneous Media, 2009, 4(1): 107-126. doi: 10.3934/nhm.2009.4.107
    [8] Dirk Helbing, Jan Siegmeier, Stefan Lämmer . Self-organized network flows. Networks and Heterogeneous Media, 2007, 2(2): 193-210. doi: 10.3934/nhm.2007.2.193
    [9] Fabio Della Rossa, Carlo D’Angelo, Alfio Quarteroni . A distributed model of traffic flows on extended regions. Networks and Heterogeneous Media, 2010, 5(3): 525-544. doi: 10.3934/nhm.2010.5.525
    [10] Tibye Saumtally, Jean-Patrick Lebacque, Habib Haj-Salem . A dynamical two-dimensional traffic model in an anisotropic network. Networks and Heterogeneous Media, 2013, 8(3): 663-684. doi: 10.3934/nhm.2013.8.663
  • Convolutional neural networks (CNNs) utilize local translation invariance in the Euclidean domain and have remarkable achievements in computer vision tasks. However, there are many data types with non-Euclidean structures, such as social networks, chemical molecules, knowledge graphs, etc., which are crucial to real-world applications. The graph convolutional neural network (GCN), as a derivative of CNNs for non-Euclidean data, was established for non-Euclidean graph data. In this paper, we mainly survey the progress of GCNs and introduce in detail several basic models based on GCNs. First, we review the challenges in building GCNs, including large-scale graph data, directed graphs and multi-scale graph tasks. Also, we briefly discuss some applications of GCNs, including computer vision, transportation networks and other fields. Furthermore, we point out some open issues and highlight some future research trends for GCNs.



    The unprecedented growth of sensing and computational capabilities have advanced the development of real-time traffic estimation techniques. However, many estimation algorithms proposed to monitor traffic conditions are only verified through experiments (e.g., [5,13,26,27,42,43]), while a theoretical analysis on the estimator performance is lacking. This is mainly due to the complexity of the models describing traffic (e.g., non-linearity and non-differentiability) [2], and, more importantly, the non-observability [30,37] of the systems subject to conservation laws. When a system is not observable, the available sensor measurements (in conjunction with the model describing system dynamics) are insufficient to correctly reconstruct the full state to be estimated. In traffic estimation problems, the non-observability issue is inevitable when a shock exists and the sensors cannot measure every state variable in the road network of interest.

    This work aims at addressing the issue of the lack of a theoretical performance analysis for traffic estimation problems under unobservable scenarios occurring at junctions. Note that in classical estimation / filtering theory, an unobservable system is very likely to result in an estimation error that diverges [1,17]. Nevertheless, in this work we derive theoretical error bounds for traffic estimation on unobservable transportation networks (with junctions), where the state estimate is provided by the Kalman filter (KF). Specifically, when the system is not observable, the error bounds are derived through leveraging the intrinsic properties of traffic models (e.g., mass conservation and the flow-density relationship), and exploring the interactions between these intrinsic properties and the update scheme in the Kalman filtering algorithm.

    The classical conservation law describing the evolution of traffic density on a road link (i.e., a road section without junctions) is the Lighthill-Whitham-Richards partial differential equation (LWR PDE) [25,32]. The cell transmission model (CTM) [7,8,23] is a discretization of the LWR PDE using the Godunov scheme [11]. In [30,35], the CTM is transformed to a hybrid linear system known as the switching mode model (SMM) that switches among different linear modes, and the observability of each mode is analyzed.

    To extend the traffic model on road links to networks, a model is needed to describe how the traffic exiting the road links on the upstream side of a junction is received by the road links on the downstream side of the junction. A well known issue is that the conservation of vehicles across the junction is insufficient to uniquely define the flows at the junction. To address this issue, a number of junction models [8,9,10,12,14,15,18,19,20,22] have been proposed via additional rules governing the distribution or priority of the flows on different road links.

    In parallel to the ongoing development of traffic models, a number of sequential traffic estimation algorithms have been proposed to integrate model predictions with real-time sensor measurements. For example, the mixture Kalman filter is applied to the SMM in [35] to estimate traffic densities for ramp metering. The parallelized particle filters and the parallelized Gaussian sum particle filter are designed in [27] for computational scalability. In [40], an efficient multiple model particle filter is proposed for joint traffic estimation and incident detection on freeways. Other treatments of traffic estimation include [5,26,29,38,41,42,43]. A comprehensive survey of sequential estimation techniques for traffic models can be found in [34].

    Although many traffic estimation algorithms proposed in the existing literature are verified experimentally, very few theoretical results exist that analyze the performance of traffic estimators (e.g., bounds on the estimation error), especially under unobservable scenarios. The main results to date are as follows. In [16], the KF is applied on a Gaussian approximation of a stochastic traffic model, and the stochastic observability of the system is proved. To ensure observability of the system, a warm-up period is required where the initial conditions are restricted to be free-flow traffic conditions. In [6], the local observability around an equilibrium traffic state is studied using a Lagrangian formulation of the traffic model. The authors of [28] prove the performance of a noise-free Luenberger observer for traffic estimation based on the SMM, which is the first work to provide theoretical performance analysis for any traffic estimator under both observable and unobservable scenarios. The Luenberger observer in [28] discards measurement feedback in unobservable modes, ensuring the spatial integral of the estimation error is conserved. Similarly in [39], the estimator runs an open-loop predictor under unobservable cases to ensure that the estimation error does not diverge. Although conserving the spatial integral of the estimation error, it is illustrated in [36] that dropping measurement feedback can lead to physically unreasonable estimates. In our earlier work [37], we showed that incorporating measurement feedback under unobservable scenarios is essential in maintaining physically reasonable estimates, i.e., due to the interactions of the model prediction and the measurement feedback in the filtering algorithm, the mean estimates of all state variables are guaranteed to be ultimately bounded inside the physically meaningful interval under unobservable modes. Note that the results in [6,16,28,37,39] are restricted to road stretches without considering junction dynamics, which is the focus of the work in this article.

    The main contribution of this article is the theoretical analysis of the estimation error bounds when using the KF to estimate traffic densities on transportation networks with junctions. To support a performance study of the KF, we first propose a switched linear system to model the evolution of traffic densities on road networks with junctions, namely the switching mode model for junctions (SMM-J). The SMM-J is an extension of the SMM, in the sense that the SMM-J describes the traffic density evolution on a road section with a junction, while the SMM only considers one-dimensional (i.e., without junctions) road sections. The SMM-J combines a switched linear system representation of the CTM with the junction model developed in [24], however, other junction models can also be incorporated in a similar fashion to derive linear traffic models on junctions. We also provide the observability result on each mode of the SMM-J, and show that nearly all modes are unobservable due to the irreversibility of the conservation laws in the presence of shocks and junctions. Compared to the one-dimensional road sections, the issue of non-observability is more frequently encountered when junctions exists, motivating attentions to the error bounds under unobservable scenarios. Next, we prove the estimation error properties of the KF that uses the SMM-J to estimate an unobservable freeway section with a junction inside. Although an unobservable system typically results in diverging estimation errors [17], we show that by combining the update scheme of the KF with the physical properties embedded in the traffic model, the following properties can be derived for traffic estimation under unobservable modes:

    1. For an unobservable road section, the Kalman gain has bounded infinity norm. This is a necessary condition to ensure bounded mean estimation error for the KF.

    2. When a road section stays in an unobservable mode, the mean estimate of each state variable is ultimately bounded inside a physically meaningful interval, thus the mean estimation error of the enire state is also ultimately bounded.

    This work complements our previous work studying the performance of traffic estimators that use the SMM to monitor unobservable one-dimensional freeway traffic conditions [37]. Thus, when estimating the traffic conditions in a large-scale road network, we can partition the traffic network into local sections which are either one-dimensional, or having a junction inside. The traffic condition in each local section is estimated by a local estimator based on the KF and the SMM-J (or the SMM). Under this distributed computing manner, the estimation errors for the sections without junctions reside below the bounds derived in [37], and the error bounds studied in this work are used to justify the estimation accuracy in the sections with junctions.

    This work is organized as follows. Section 2 reviews the KF and its error properties under observable and unobservable systems, and briefly summarizes the CTM. Section 3 introduces the SMM-J, its observability under different modes, and the properties of the state transition matrices that reflect the intrinsic physical properties of the traffic model. The properties of the state transition matrices of the SMM-J are applied in Section 4, where we prove the boundedness of the Kalman gain and the ultimate bound of the mean estimation error under unobservable scenarios. Finally, some concluding remarks are provided in Section 5.

    Notations. Let In and 0n,m be the n×n identity matrix and the n×m zero matrix, respectively. The subscripts of In and 0n,m are sometimes omitted, when dimensionality is clear from the context. Denote as E[] the expectation operator, and the "bar" symbol is used to denote the expected value of random vector x, i.e., ˉx=E[x]. The symbol is used to denote the transpose operator.

    In this section, we first review the Kalman filter and the properties of its error covariance as well as mean estimation error under observable and unobservable scenarios. We also provide a brief overview of the cell transmission model used to construct the SMM-J.

    In this subsection, we briefly review the KF and introduce necessary notations in this article. Consider a general linear time-varying system

    ρk+1=Akρk+uk+ωk,     ρkRn, (1)
    zk=Hkρk+vk,     zkRm, (2)

    where ρk and zk are the state vector and sensor measurement vector at time kN, respectively. The matrices Ak and Hk are the state transition matrix and the observation matrix at time k. The term uk in (1) is a deterministic system input. The noise terms ωkN(0,Qk) and vkN(0,Rk) are the white Gaussian model and measurement noise, where Qk and Rk denote the model and the measurement error covariance matrices at time k. Given the sensor data up to time k denoted by Zk={z0,,zk}, the prior estimate and posterior estimate of the state can be expressed as ρk|k1=E[ρk|Zk1] and ρk|k=E[ρk|Zk], respectively. Let ηk|k1=ρk|k1ρk and ηk|k=ρk|kρk denote the prior and posterior estimation errors. The estimation error covariance matrices associated with ρk|k1 and ρk|k are given by Γk|k1=E[ηk|k1ηk|k1|Zk1] and Γk|k=E[ηk|kηk|k|Zk]. The KF sequentially computes ρk|k from ρk1|k1 as follows:

    Prediction:{ρk|k1=Ak1ρk1|k1+ukΓk|k1=Ak1Γk1|k1Ak1+Qk1, (3)
    Correction:{ρk|k=ρk|k1+Kk(zkHkρk|k1)Γk|k=Γk|k1KkHkΓk|k1Kk=Γk|k1Hk(Rk+HkΓk|k1Hk)1. (4)

    In (4), the matrix Kk is denoted as the Kalman gain at time k. Note that for all k, the state estimates ρk|k1 and ρk|k are random vectors. The mean posterior estimate and the mean posterior estimation error1 are denoted as ˉρk|k and ˉηk|k, respectively.

    1For the remainder of this article, the term state estimates/estimation errors/error covariance refers to the posterior estimates, unless specified otherwise.

    Observability. The discrete system (1)-(2) is uniformly completely observable if there exists a positive integer N and positive constants α, β such that

    αIn<Ik,kN<βIn,    for all kN, (5)

    where Ik1,k0 is defined as the information matrix for time interval k[k0,k1]:

    Ik1,k0=k1k=k0Ξk,k1HkR1kHkΞk,k1,

    where

    Ξk,k1=k11κ=kA1κ,   and   Ξk1,k=Ξ1k,k1=kκ=k11Aκ. (6)

    The observability of a system characterizes whether the sensor measurements of the system is sufficient for the KF to correctly estimate the state vector. Given the positive definiteness of the information matrix, the observability grammian matrix linking the the initial state ρ0 to the sensor measurements up to time N (i.e., ZN) is invertible. The next lemma states the boundedness (both from below and above) of the estimation error covariance and the convergence (to zero) of the estimation error, when using the KF (3)-(4) to estimate a uniformly completely observable system.

    Lemma 1 (Chapter 7.6 in [17]). If the dynamical system (1)-(2) is uniformly completely observable and the following conditions hold:

    (C.1): there exist positive constants q1, q2, r1 and r2 such that q1In<Qk<q2In and r1Im<Rk<r2Im for all k;

    (C.2): the initial error covariance is positive definite, i.e., Γ0|0>0;

    (C.3): the state transition matrix Ak is nonsingular for all k,

    then there exist positive constants c1>0 and c2>0 such that the error covariance of the KF (3)-(4) satisfies

    c1In<Γk|k<c2In,   for all k0.

    Moreover, there exists positive constants a>0 and 0<q<1 such that the 2-norm2 of the mean estimation error satisfies

    2For the remainder of this article, we denote as the 2-norm of a matrix or a vector.

    ˉηk|k<aqkˉη0|0,   for all k0.

    When system (1)-(2) is not observable, the mean estimation error ˉηk|k will diverge, unless the unobservable part of the state is bounded or converges to zero automatically. In Appendix.1, we present an example illustrating the evolution of the mean estimation error given by the KF when tracking an unobservable system.

    The classical conservation law describing the evolution of traffic density ρ(t,x) on a road at location x and time t is the Lighthill-Whitham-Richards partial differential equation (LWR PDE) [25,32]:

    tρ+xF(ρ)=0. (7)

    The function F(ρ)=ρv(ρ) is called the flux function, where v(ρ) is an empirical velocity function used to close the model.

    The cell transmission model (CTM) [7,8,23] is a discretization of (7) using a Godunov scheme [11]. Consider a uniformly sized discretization grid defined by a space step Δx>0 and a time step Δt>0. Let l index the cell defined by x[lΔx,(l+1)Δx), and denote as ρlk the density at time kΔt in cell l, where kN and lN+. Moreover, denote as f(ρl1k,ρlk) the flux between cell l1 and l. In the CTM, the discretized model (7) becomes

    ρlk+1=ρlk+ΔtΔx(f(ρl1k,ρlk)f(ρlk,ρl+1k)), (8)

    where f(ρl1k,ρlk) is computed by

    f(ρl1k,ρlk)=min{s(ρl1k),r(ρlk)}. (9)

    In (9), s(ρl1k) is the sending capacity (i.e., maximum sending flow) of cell l1 at time k, which is a function of ρl1k, and r(ρlk) is the receiving capacity (i.e., maximum receiving flow) of cell l at time k, which is a function of ρlk. Note that if the Courant-Friedrichs-Lewy (CFL) condition is satisfied, the solution of the CTM converges in L1 to the weak solution of the LWR PDE as Δx0 [33].

    Remark 1. Note that the terminologies sending capacity and receiving capacity are equivalent to the notions of demand and supply. Both sending/receiving and demand/supply terminologies are widely used in the traffic community, with the former introduced in [7,8], and the latter introduced in [23]. In this work we use the sending/receiving terminology, which is consistent throughout the article, and is also consistent with our previous work [37].

    The flux function [8] used in this work is the triangular flux function (shown in Figure 1) given by

    Figure 1.  The triangular fundamental diagram in (10).
    F(ρ)={ρvmif ρ[0,ϱc]w(ϱmρ)if ρ[ϱc,ϱm]  (10)

    where w=ϱcvmϱmϱc, vm denotes the freeflow speed, and ϱm denotes the maximum density. The parameter ϱc is the critical density at which the maximum flux is realized. For the triangular fundamental diagram, the flux function has different slopes in freeflow (0<ρϱc) and congestion (ϱc<ρϱm). In freeflow, the slope is vm, and in congestion, it is w. Under the triangular flux function, the sending and receiving capacities are determined by:

    s(ρ)={ρvmif ρ[0,ϱc]qmif ρ[ϱc,ϱm] r(ρ)={qmif ρ[0,ϱc]w(ϱmρ)if ρ[ϱc,ϱm]  (11)

    where qm is the maximum flow given by qm=vmϱc.

    In this section, we derive the hybrid linear model describing traffic density evolution on a road section with a junction, namely the switching mode model for junctions (SMM-J). The SMM-J combines a switched linear system representation of the CTM (i.e., the CTM where the flux function is the triangular fundamental diagram) with a junction solver. This section starts with a review of the applied junction solver. Next, we introduce the SMM-J and provide examples regarding its explicit formulas. Finally, the observability of the SMM-J is discussed.

    This subsection introduces the junction solver proposed in [24]. As shown in Figure 2a, the junction solver computes flux f(ρlk,ρik) and f(ρlk,ρjk) between the connecting cells l, i and j forming a diverge junction. In the merge junction shown in Figure 2b, the junction solver computes f(ρik,ρlk) and f(ρjk,ρlk) between the connecting cells. This solver is later applied in Section 3.2 to develop the SMM-J.

    Figure 2.  A diverge and a merge junction connected by three cells indexed by i, j, and l.

    At a diverge junction in Figure 2a, the junction solver is governed by the following rules:

    (R.1): The mass across the junction is conserved.

    (R.2): The throughput flow f(ρlk,ρik)+f(ρlk,ρjk), i.e., the outgoing flow of cell l, is maximized subject to the maximum flow that can be sent or received on each connecting cell.

    (R.3): The distribution of flux f(ρlk,ρik) and f(ρlk,ρjk) satisfies f(ρlk,ρjk)=αdf(ρlk,ρik), where αd is the prescribed distribution parameter that models the routing preference to the downstream cells. When (R.3) conflicts (R.2), i.e., the flow solution that satisfies the distribution equation does not maximize the throughput, then (R.3) is relaxed, such that the solution satisfies (R.2) and minimizes the deviation from the prescribed distribution parameter, e.g., |f(ρlk,ρjk)/f(ρlk,ρik)αd|.

    The diverge junction solver is posed as a convex program with a carefully constructed objective function to accommodate the throughput maximization (R.2) and the flow distribution (R.3). The mathematical formula of the diverge junction solver is given below (see [24,Section 3.2] for more details).

    Definition 1 (Convex program for the diverge junction solver). Define the objective function J(f1,f2) as:

    J(f1,f2)=(1λ)(f1+f2)λ(f2αdf1)2,

    where 0<λ<1 and λ is chosen such that Jf1>0 and Jf2>03. The conditions on λ is used to prioritize maximizing the throughput f(ρlk,ρik)+f(ρlk,ρjk) (as stated in (R.2)), then minimizing the deviation from the prescribed distribution parameter αd (as stated in (R.3)). The fluxes f(ρlk,ρik) and f(ρlk,ρjk) are obtained by solving the following convex program:

    3One possible choice of λ is λ=min{(1+2α2dqm+ε)1,(1+2qm+ε)1}, where ε>0 can be any positive value.

    f(ρlk,ρik), f(ρlk,ρjk) = argmaxf1,f2 J(f1,f2)s.t.  f1r(ρik) (12)
    f2r(ρjk) (13)
    f1+f2s(ρlk). (14)

    Figure 3 provides a graphical illustration for the solutions of the convex program defined in Definition 1. The blue vertical solid line denotes the receiving capacity of cell i, i.e., r(ρik), and the blue horizontal solid line denotes the receiving capacity of cell j, i.e., r(ρjk). The intercepts of the blue dashed line (with slope -1) denote the sending capacity of cell l, i.e., s(ρlk). The shaded area denotes the feasible values of the flux from cell l to i and the flux from cell l to j, the feasible area is obtained based on (12)-(14). The slope of the black dotted line is the prescribed distribution ratio αd. The fluxes computed by the junction solver in Definition 1 is marked by the red dot, whose horizontal axis and vertical axis values are the obtained f(ρlk,ρik) and f(ρlk,ρjk), respectively.

    Figure 3.  Three scenarios in the junction solver [24] for the diverge junction shown in Figure 2a, where cell l diverges to cell i and cell j. The blue vertical (resp. horizontal) solid line denotes the receiving capacity of cell i (resp. cell j). The intercepts of the blue dashed line denote the sending capacity of cell l. The shaded area denotes the feasible values of the flux from cell l to i and the flux from cell l to j. The slope of the black dotted line is the prescribed distribution ratio αd. The fluxes computed by the junction solver is marked by the red dot, whose horizontal axis and vertical axis values are the obtained f(ρlk,ρik) and f(ρlk,ρjk), respectively. Note that in diverge case Ⅱ and diverge case Ⅲ, the receiving capacities of cell i and cell j are not necessarily smaller than the sending capacity of cell l, and the graphical illustration of the flux solutions is also applicable for r(ρik)s(ρlk) and/or r(ρjk)s(ρlk)..

    According to the convex program in Definition 1, to obtain f(ρlk,ρik) and f(ρlk,ρjk) we need to find the solution point (i.e., the red dot) in Figure 3 that satisfies the following requirements:

    ● The point lies in the shaded feasible area, so that conditions (12)-(14) are satisfied;

    ● The point is as close as possible to the blue dashed line (with slope -1), so that the throughput f(ρlk,ρik)+f(ρlk,ρjk) is maximized; this is due to the fact that the distance d0 between the point and the blue dashed line is proportional to the disparity between the sending capacity of cell l and the throughput, i.e., |s(ρlk)(f(ρlk,ρik)+f(ρlk,ρjk))|=2d0 (as illustrated in diverge case Ⅰ of Figure 3);

    ● Conditioned on prioritizing maximizing the throughput, the point is as close as possible to the black dotted line (with slope αd), so that the distribution ratio is respected; this means that when maximizing the throughput conflicts with the distribution ratio, the requirement f(ρlk,ρjk)=αdf(ρlk,ρik) can be relaxed.

    As shown in Figure 3, there are in total three scenarios depending on the values of s(ρlk), r(ρik) and r(ρjk). The three scenarios are: (i) diverge case Ⅰ, when s(ρlk)r(ρik)+r(ρjk); (ii) diverge case Ⅱ, when s(ρlk)<r(ρik)+r(ρjk), and the prescribed distribution ratio αd can be followed exactly; and (iii) diverge case Ⅲ, when s(ρlk)<r(ρik)+r(ρjk), but (due to throughput maximization) the prescribed distribution ratio αd cannot be followed exactly.

    Under diverge case Ⅰ, the fluxes f(ρlk,ρik) and f(ρlk,ρjk) are computed by:

    f(ρlk,ρik)=r(ρik),   f(ρlk,ρjk)=r(ρjk). (15)

    Under diverge case Ⅱ, the fluxes f(ρlk,ρik) and f(ρlk,ρjk) are given as follows:

    f(ρlk,ρik)=1αd+1s(ρlk),   f(ρlk,ρjk)=αdαd+1s(ρlk). (16)

    Under diverge case Ⅲ, the junction solver first finds the two vertices of the shaded area that lie on the dashed line, and next define the point closer to the dotted line as the flux solutions f(ρlk,ρik) and f(ρlk,ρjk). Hence, depending on the magnitude of s(ρlk), r(ρik) and r(ρjk), the solutions could be either

    f(ρlk,ρik)=r(ρik),  f(ρlk,ρjk)=s(ρlk)r(ρik), (17)

    or

    f(ρlk,ρik)=s(ρlk)r(ρjk),  f(ρlk,ρjk)=r(ρjk). (18)

    Note that the diverge case Ⅲ shown in Figure 3 illustrates the flux solutions presented in (17).

    Remark 2. The diverge junction solver described above is a non-First-In-First-Out (FIFO) model [8,10]. The FIFO diverge model maximizes the outgoing flow of cell l subject to the distribution ratio f(ρlk,ρjk)=αdf(ρlk,ρik). Although the FIFO model circumvents the conflicts between throughput maximization and flow distribution, it produces unrealistic solutions in some circumstances. Several diverge junction models have been proposed to resolve this issue [14,20,22]. In the same spirit of these models, the diverge junction solver applied in this article is developed to produce similar traffic condition dependent solutions without introducing additional complexity on the traffic dynamics [24]. As a related note, the results proved in this article can be extended to FIFO models with minor changes to the proof.

    At a merge junction in Figure 2b, the junction solver conserves mass, and maximizes the throughput while minimizing the deviation from a prescribed priority parameter αp denoting the flow assignment ratio f(ρjk,ρlk)=αpf(ρik,ρlk). This priority equation is relaxed if it conflicts with flow maximization. The reader is referred to [10,12] for a detailed description of the merge model.

    The structure of the diverge and merge models are similar, in the sense that both maximize the throughput while minimizing the deviation from the prescribed distribution or priority parameters. Therefore, the remainder of this article focuses on deriving the linear traffic model and analyzing the performance of the KF on the road network with a diverge junction. The analysis can be transferred to the merge case via combining the merge junction solver with the switched linearized representation of the CTM, exploring the properties of the resulting state transition matrices as in the diverge case, and analyzing the effect of these properties on the boundedness of the Kalman gain and the mean estimation error.

    As stated in Section 1.2, when monitoring traffic on large-scale networks, the road network is partitioned into local sections which are either one-dimensional, or having a junction inside. The traffic states on the one-dimensional local sections evolve according to the SMM, and the SMM-J is used to describe the evolution of traffic states on local sections with junctions.

    As shown in Figure 4, consider a local section with n cells, three links and a junction. The number of cells on each link is n1, n2, and n3, respectively, with n1+n2+n3=n. The state variable at time kN is constructed as ρk=(ρ1k,,ρn1k,ρn1+1k,,ρn1+n2k,ρn1+n2+1k,,ρnk). As a common treatment [28,30,35,38,39], the boundary flows, denoted by ϕ1k, ϕ2k, and ϕ3k, are considered to be deterministic system inputs (please refer to [3] for the concept of using ghost cells to compute boundary flows using boundary state measurements). The SMM-J describes the evolution of ρk using a switched linear dynamics, and is derived under the following assumptions:

    Figure 4.  A local section with n cells, three links and a junction.

    (A.1): For each local section, there is at most one transition between freeflow and congestion in each of the three links.

    (A.2): The three connecting cells forming the junction (i.e., cell n1, n1+1 and n1+n2+1 in Figure 4) are either all in freeflow or all in congestion.

    Assumption (A.1) is practically meaningful since the local sections are usually partitioned sufficiently short such that at most one queue is growing or dissipating within each link, which is also a commonly used assumption in the SMM [28,30,35,37,39]. Assumption (A.2) is imposed to simplify the model by reducing the number of modes considered. Note that when (A.2) is relaxed, the number of modes is greatly increased, but without yielding new insights into the estimation performance at junctions. The analysis in this work still holds, the only difference is to consider an enormously increased number of modes.

    Given the assumptions stated above, on each local section with a junction, the SMM-J may switch among 32 modes (defined in Table 1) depending on (i) the freeflow/congestion status of the boundary cells and the connecting cells near the junction, and (ii) the flux solution of the junction solver characterized by the three scenarios shown in Figure 3.

    Table 1.  Mode definition and observability of the SMM-J.
    Mode F/C1 status of cell(s) Transition3 on link Diverge case Obser-vability4
    1 n1+n2 n near junction2 1 2 3
    1 F F F F none none none O
    2 F F F C Sh. Ep. Ep. U
    3 F F F C Sh. Ep. Ep. U
    4 F F F C Sh. Ep. Ep. U
    5 C C C C none none none U
    6 C C C C none none none U
    7 C C C C none none none U
    8 C C C F Ep. Sh. Sh. U
    9 F C C C Sh. none none U
    10 F C C C Sh. none none U
    11 F C C C Sh. none none U
    12 F C C F none Sh. Sh. U
    13 C C F C none none Ep. U
    14 C C F C none none Ep. U
    15 C C F C none none Ep. U
    16 C C F F Ep. Sh. none U
    17 C F C C none Ep. none U
    18 C F C C none Ep. none U
    19 C F C C none Ep. none U
    20 C F C F Ep. none Sh. U
    21 C F F F Ep. none none O
    22 C F F C none Ep. Ep. U
    23 C F F C none Ep. Ep. U
    24 C F F C none Ep. Ep. U
    25 F C F F none Sh. none U
    26 F C F C Sh. none Ep. U
    27 F C F C Sh. none Ep. U
    28 F C F C Sh. none Ep. U
    29 F F C F none none Sh. U
    30 F F C C Sh. Ep. none U
    31 F F C C Sh. Ep. none U
    32 F F C C Sh. Ep. none U
    1 "F" and "C" stand for freeflow and congestion, respectively.
    2 Cells indexed by n1, n1+1 and n1+n2+1.
    3 "Sh." and "Ep." stand for shock (i.e., transition from freeflow to congestion) and expansion fan (i.e., transition from congestion to freeflow), respectively.
    4 "O" stands for uniformly completely observable and "U" stands for unobservable. Note that the observability results are derived under sensor locations shown in Figure 4.

     | Show Table
    DownLoad: CSV

    In the SMM-J, the density update scheme for the interior cells in each link (i.e., cells indexed by l{2,,n11}{n1+2,,n1+n21}{n1+n2+2,,n1}) is given by (8), where the flow between two adjacent cells is computed according to (9). For the three boundary cells, their density updates are given as follows:

    ρ1k+1=ρ1k+ΔtΔx(ϕ1kf(ρ1k,ρ2k)),ρn1+n2k+1=ρn1+n2k+ΔtΔx(f(ρn1+n21k,ρn1+n2k)ϕ2k),ρnk+1=ρnk+ΔtΔx(f(ρn1k,ρnk)ϕ3k),

    where f(ρ1k,ρ2k), f(ρn1+n21k,ρn1+n2k) and f(ρn1k,ρnk) are also obtained from (9). The density update scheme for the three cells near the junction reads:

    ρn1k+1=ρn1k+ΔtΔx(f(ρn11k,ρn1k)f(ρn1k,ρn1+1k)f(ρn1k,ρn1+n2+1k)),ρn1+1k+1=ρn1+1k+ΔtΔx(f(ρn1k,ρn1+1k)f(ρn1+1k,ρn1+2k)),ρn1+n2+1k+1=ρn1+n2+1k+ΔtΔx(f(ρn1k,ρn1+n2+1k)f(ρn1+n2+1k,ρn1+n2+2k)),

    where f(ρn11k,ρn1k), f(ρn1+1k,ρn1+2k), and f(ρn1+n2+1k,ρn1+n2+2k) are computed by (9), and the flows between neighboring cells (i.e., f(ρn1k,ρn1+1k) and f(ρn1k,ρn1+n2+1k)) are computed based on the junction solver discussed in Section 3.1.

    When applying the triangular fundamental diagram (10) to compute the flow across the cells, the traffic state ρk in a local section evolves with linear dynamics in each mode stated in Table 1, forming a hybrid system:

    ρk+1=Akρk+Bρk1ϱm+Bqk1qm+Bϕkϕk, (19)

    where 1 is the vector of all ones, the vector ϕk=(ϕ1k,ϕ2k,ϕ3k), and AkRn×n, BρkRn×n, BqkRn×n, BϕkRn×3 are constructed based on the current mode of the local section, the locations of the shocks and expansion fans (if they exist), and the moving direction of the shocks.

    The next two examples demonstrate the construction of matrices Ak, Bρk, Bqk and Bϕk. Specifically, the construction of matrices Ak provides insights on the properties of the state transition matrices of the SMM-J that reflect the intrinsic physical properties of the traffic model. These properties are critical in proving the estimation error bounds of the KF on traffic networks. Before showing the examples, we first introduce some notation which will be used as elements of the matrices to be constructed. For pN+, define ΘpRp×p and ΔpRp×p by their (i,j)th entries as

    Θp(i,j)={1vmΔtΔxif i=jvmΔtΔxif i=j+10otherwise,  (20)
    Δp(i,j)={1wΔtΔxif i=jwΔtΔxif i=j10otherwise. (21)

    For p1N+, p2N+, p3N+ and p4N+, define Ep3,p4p1,p2Rp1×p2 as the p1×p2 matrix with all entries zero except its (p3,p4)th entry, which is one. Explicitly,

    Ep3,p4p1,p2(i,j)={1if i=p3 and j=p40otherwise. (22)

    Moreover, define ˜ΘpRp×p and ˜ΔpRp×p as:

    ˜Θp={(Θp10p1,1vmΔtΔxE1,p11,p11)if p21if p=1

    and

    ˜Δp={(1wΔtΔxE1,11,p10p1,1Δp1)if p21if p=1.

    Example 1 (System dynamics of the SMM-J under Mode 1). Consider the local section in Figure 4 where all the cells are in freeflow. Within a single link, the flux between two neighboring cells indexed by i and i+1 is given by f(ρik,ρi+1k)=vmρik. At the junction, it holds that s(ρn1k)=vmρn1k<r(ρn1+1k)+r(ρn1+n2+1k)=2qm. Also note that s(ρn1k)r(ρn1+1k)=qm and s(ρn1k)r(ρn1+n2+1k)=qm, the distribution ratio αd can be followed exactly. Hence, the state is under Mode 1 at time k, and the junction solver computes fluxes f(ρn1k,ρn1+1k) and f(ρn1k,ρn1+n2+1k) according to diverge case Ⅱ (16) as follows:

    f(ρn1k,ρn1+1k)=ρn1kvm1+αd,   f(ρn1k,ρn1+n2+1k)=αdρn1kvm1+αd.

    Substituting the flows computed above into the update scheme of the traffic density on each cell, it follows that the explicit forms of Ak, Bρk, Bqk, and Bϕk in (19) are

    Ak=(Θn1vmΔt(1+αd)ΔxE1,n1n2,n1˜Θn2αdvmΔt(1+αd)ΔxE1,n1n3,n1˜Θn3),   Bρk=Bqk=0n,n,Bϕk=ΔtΔx(E1,1n,3En1+n2,2n,3En,3n,3) (23)

    in Mode 1. Note that in the above definitions and for the remainder of this subsection, blocks in the matrices which are left blank are zeros everywhere.

    Example 2 (System dynamics of the SMM-J under Modes 2-4). Consider the local section in Figure 4 where the three boundary cells indexed by 1, n1+n2 and n are all in freeflow, and the three cells near the junction, i.e., the cells indexed by n1, n1+1 and n1+n2+1 are in congestion. Given the assumption that there is at most one transition between freeflow and congestion in each of the three links connecting the junction, it can be concluded that there is a shock (i.e., transition from freeflow to congestion) on link 1, while link 2 and link 3 each has an expansion fan. Let l1 be the location of the shock on link 1, i.e., the transition from freeflow to congestion on link 1 occurs between cell l1 and l1+1. Moreover, we define

    ˜l1={l1if the shock has positive velocity or is stationaryl11if the shock has negative velocity, 

    and

    ˆl1=n11˜l1,

    which are later used to simplify the notations to define matrices Ak, Bρk, Bqk, and Bϕk. Similarly, denote as l2 (resp. l3) the location of the expansion fan on link 2 (resp. link 3), i.e., the transition from congestion to freeflow on link 2 (resp. link 3) occurs between cells l2 and l2+1 (resp. cells l3 and l3+1). To simplify the notation, we also define

    ˜l2=l2n1,   ˆl2=n2˜l2,   ˜l3=l3n1n2,   ˆl3=n3˜l3.

    At the junction, the sending capacity of cell n1 is s(ρn1k)=qm, and the receiving capacities of cell n1+1 and cell n1+n2+1 are r(ρn1+1k)=w(ϱmρn1+1k) and r(ρn1+n2+1k)=w(ϱmρn1+n2+1k), respectively. Depending on the magnitudes of s(ρn1k), r(ρn1+1k), and r(ρn1+n2+1k), the junction solver follows one of the three possible scenarios shown in Figure 3.

    1. Diverge case Ⅰ: when s(ρn1k)r(ρn1+1k)+r(ρn1+n2+1k). In this case, the state is under Mode 2 at time k, and the junction solver computes fluxes f(ρn1k,ρn1+1k) and f(ρn1k,ρn1+n2+1k) according to diverge case Ⅰ (15) as follows:

    f(ρn1k,ρn1+1k)=r(ρn1+1k)=w(ϱmρn1+1k),f(ρn1k,ρn1+n2+1k)=r(ρn1+n2+1k)=w(ϱmρn1+n2+1k).

    Hence in Mode 2, the explicit forms of Ak, Bρk, Bqk, and Bϕk in (19) are

    Ak=(Θ˜l1vmΔtΔxE1,˜l11,˜l11wΔtΔxE1,11,ˆl1Δˆl1wΔtΔxEˆl1,1ˆl1,˜l2wΔtΔxEˆl1,1ˆl1,˜l3Δ˜l2˜Θˆl2Δ˜l3˜Θˆl3),
    Bρk=wΔtΔx(E˜l1+1,˜l1+2n,nEn1,n1+n2+1n,n+El2,l2n,n+El3,l3n,n),Bqk=ΔtΔx(El2.l2n,n+El2+1,l2n,nEl3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3En1+n2,2n,3En,3n,3).

    2. Diverge case Ⅱ: when s(ρn1k)<r(ρn1+1k)+r(ρn1+n2+1k), and the prescribed distribution ratio αd can be followed exactly. In this case, the state is under Mode 3 at time k, and the junction solver computes fluxes f(ρn1k,ρn1+1k) and f(ρn1k,ρn1+n2+1k) according to diverge case Ⅱ (16) as follows:

    f(ρn1k,ρn1+1k)=1αd+1s(ρn1k)=1αd+1qm,f(ρn1k,ρn1+n2+1k)=αdαd+1s(ρn1k)=αdαd+1qm.

    In Mode 3, the explicit forms of Ak, Bρk, Bqk, and Bϕk in (19) are

    Ak=(Θ˜l1vmΔtΔxE1,˜l11,˜l11wΔtΔxE1,11,ˆl1Δˆl1˜Δ˜l2˜Θˆl2˜Δ˜l3˜Θˆl3),
    Bρk=wΔtΔx(E˜l1+1,˜l1+2n,n+En1,n1n,nEn1+1,n1+2n,n+El2,l2n,nEn1+n2+1,n1+n2+2n,n+El3,l3n,n),Bqk=ΔtΔx(En1+n1n,n+11+αdEn1+1,n1n,n+αd1+αdEn1+n2+1,n1n,nEl2,l2n,n+El2+1,l2n,nEl3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3En1+n2,2n,3En,3n,3).

    3. Diverge case Ⅲ: when s(ρn1k)<r(ρn1+1k)+r(ρn1+n2+1k), but the prescribed distribution ratio αd cannot be followed exactly. In this case, the state is under Mode 4 at time k. Depending on the magnitudes of s(ρn1k), r(ρn1+1k) and r(ρn1+n2+1k), the fluxes f(ρn1k,ρn1+1k) and f(ρn1k,ρn1+n2+1k) computed by the junction solver are either obtained from (17), i.e.,

    f(ρn1k,ρn1+1k)=r(ρn1+1k)=w(ϱmρn1+1k),f(ρn1k,ρn1+n2+1k)=s(ρn1k)r(ρn1+1k)=qmw(ϱmρn1+1k), (24)

    or obtained from (18), i.e.,

    f(ρn1k,ρn1+1k)=s(ρn1k)r(ρn1+n2+1k)=qmw(ϱmρn1+n2+1k),f(ρn1k,ρn1+n2+1k)=r(ρn1+n2+1k)=w(ϱmρn1+n2+1k). (25)

    For conciseness of the presentation, we provide next the explicit formulas of Ak, Bρk, Bqk, and Bϕk when the fluxes are computed according to (24), and the construction of the system dynamics when the fluxes are given by (25) can be done in a similar fashion. The matrices Ak, Bρk, Bqk, and Bϕk read

    Ak=(Θ˜l1vmΔtΔxE1,˜l11,˜l11wΔtΔxE1,11,ˆl1Δˆl1wΔtΔxEˆl1,1ˆl1,˜l2Δ˜l2˜Θˆl2wΔtΔxE1,1˜l3,˜l2˜Δ˜l3˜Θˆl3),
    Bρk=wΔtΔx(E˜l1+1,˜l1+2n,n+El2,l2n,nEn1+n2+1,n1+n2+2n,nEn1+n2+1,n1+1n,n+El3,l3n,n),Bqk=ΔtΔx(El2.l2n,n+El2+1,l2n,n+En1+n2+1,n1+1n,nEl3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3En1+n2,2n,3En,3n,3).

    Some properties of the state transition matrix Ak are summarized below, which will be demonstrated in Section 4.1 to assume important roles in proving the boundedness of the Kalman gain (a necessary condition to ensure the ultimate boundedness of the mean estimation error) when using the KF to estimate traffic conditions based on the SMM-J.

    (P.1): For Ak in all modes, each element satisfies

    0Ak(r,c)1,for all kN and r,c{1,,n}.

    This property is due to the CFL condition [33] in the discretization scheme (8).

    (P.2): When Ak is derived under diverge case Ⅰ and diverge case Ⅱ, the sum of the elements in Ak at the same column c satisfies

    nr=1Ak(r,c)1,for all kN and c{1,,n}.

    This property is due to the CFL condition as in (P.1) and the conservation law embedded in the traffic model.

    (P.3): When Ak is derived under diverge case Ⅲ, the sum of the elements in Ak at the same column c satisfies

    nr=1Ak(r,c)1,for all kN and c{c|c{1,,n},c}

    where =n1+1 if f(ρn1k,ρn1+1k)=r(ρn1+1k) and =n1+n2+1 if f(ρn1k,ρn1+1k)=s(ρn1k)r(ρn1+n2+1k). Moreover, it also holds that for Ak under diverge case Ⅲ,

    Ak(r,c)=0,for all kr{n1+1,,n} and c{1,n1}.

    This is due to the facts that (i) the flows from cell n1 at the junction to the two downstream cells (i.e., cell n1+1 and cell n1+n2+1) do not depend on the densities of the cells on link 1, as shown in (24)-(25), and (ii) the internal flows between adjacent cells on link 2 and link 3 are also independent of the densities of the cells on link 1.

    Based on the above properties, the following lemma derives the bounds on each entry of the product of the state transition matrices, which will later be applied to prove the boundedness of the Kalman gain (see Lemma 3).

    Lemma 2. Consider the local section in Figure 4 that stays inside a SMM-J mode while k(k0,k1]4, where 0k0<k1+. Recall from (6) that the product of the state transition matrices is defined as

    4Recall that the time instant kN, hence k(k0,k1] denotes k{k0+1,,k1}.

    Ξk+1,k0+1=k0+1κ=kAκ,   for k(k0,k1]. (26)

    The (i,j)th entry of Ξk+1,k0+1 satisfies

    0Ξk+1,k0+1(i,j)1  for all k(k0,k1]  and  i,j{1,,n}. (27)

    Proof. The proof applies properties (P.1)-(P.3), and is reported in Appendix.2.

    From an estimation point of view, it is assumed that the sensors are located on the far ends of the three links connecting the junction (as illustrated in Figure 4), measuring the densities of the boundary cells of the local section (i.e., ρ1k, ρn1+n2k and ρnk).

    Incorporating model noise in the SMM-J (19) yields:

    ρk+1=Akρk+uk+ωk,    ρkRn, (28)

    where ωkN(0,Qk) is the white Gaussian model noise, and define the deterministic system input as:

    uk=Bρk1ϱm+Bqk1qm+Bϕkϕk.

    The sensor measurements are modeled as follows:

    zk=Hkρk+vk,    zkR3, (29)

    where the observation matrix Hk=E1,13,n+E2,n1+n23,n+E3,n3,n, and vkN(0,Rk) is the white Gassian measurement noise. Hence, as shown in (28)-(29), the system dynamics of the SMM-J is rewritten in the form of (1)-(2).

    The observability of system (28)-(29) under different modes are listed in Table 1, which can be derived directly from the definition of observability stated in Section 2.1, i.e., checking the boundedness of the information matrix. According to Table 1, most of the modes are not observable except (i) when all cells in the local section are in freeflow, and (ii) when an expansion fan sits on link 1 and no other transitions between freeflow and congestion exist in the local section. From a physical viewpoint, the non-observability of the SMM-J is due to the irreversibility of the vehicle conservation law given the available sensor measurements in the presence of shocks, and the presence of the junction. It is indicated that compared to the observability of the SMM [30], the issue of non-observability is more critical when junctions exist. For example, a one-dimensional road section where the traffic is in congestion everywhere is observable given measurements of the upstream boundary cell [30], while a congested local section with a junction is not observable even with the measurements of all the three boundary cells (as shown by the cases for Modes 5-7). The performance of the KF under uniformly completely observable systems is widely studied (as summarized in Lemma 1). In this article, we focus on analysing the theoretical performance of the KF under the unobservable modes of the SMM-J.

    Challenges for estimating an unobservable system stem from the fact that the estimation error covariance could grow unbounded, thus the mean estimation error also potentially diverges (as shown in Example 3 in the appendix). In this subsection, we show that when combining the physical properties of the traffic model (i.e., vehicle conservation and the flow-density relationship) with the update scheme of the KF, the mean estimation errors of all the cells in an unobservable local section are ultimately bounded inside (ϵ,ϱm+ϵ) for all ϵ>0, provided that the density measurements of the three boundary cells are available. This ensures that the mean estimates of the KF for unobservable modes are always physically meaningful to within ϵ. Comparatively, it is shown in [36] that an open-loop observer may result in non-physical state estimates in unobservable modes.

    Note that the three conditions (C.1)-(C.3) in Lemma 1 are necessary for proving the properties of the KF for traffic estimation under unobservable systems. For system (28)-(29), we assume that conditions (C.1) and (C.2) can be ensured when setting up the parameters in the KF. It can also be directly verified that condition (C.3) always holds for all the modes of the SMM-J.

    Let (kU0,kU1] be the time interval inside which the local section shown in Figure 4 stays in an unobservable mode of the SMM-J. In this subsection, we present a lemma stating the boundedness of the Kalman gain for k(kU0,kU1], which is obtained based on the boundedness of the cross-covariance of the observable and unobservable subsystems in the Kalman observability canonical form (see Appendix.3). According to the KF update scheme in (4), the boundedness of the Kalman gain is a necessary condition for the boundedness of the state estimate.

    Lemma 3. Consider an unobservable local section shown in Figure 4. The local section stays inside an unobservable mode of the SMM-J while k(kU0,kU1], where 0kU0<kU1+. Given density measurements of the three boundary cells, the infinity norm5 of the Kalman gain computed by the KF (3)-(4) satisfies

    5Recall that for matrix MRp×q, its infinity norm is defined as M=maxr{1,,p}qc=1|M(r,c)|.

    Kkk(ΓkU0|kU0),for all k(kU0,kU1], (30)

    where k() is a function of the error covariance at time kU0.

    Proof. The explicit formula of k(ΓkU0|kU0) is presented in Appendix.4.1, and is derived in Appendix.4.2.

    In the proof of Lemma 3, the Kalman gain is partitioned into blocks corresponding to the observable and unobservable subsystems (as shown in (49)). The part corresponding to the observable subsystem is a function of the estimation error covariance of the observable subsystem (see (50)), thus its boundedness is relatively straightforward to justify. On the other hand, the block of the Kalman gain that corresponds to the unobservable subsystem is a function of the cross-covariance of the observable and the unobservable subsystems (see (51)). By exploring the interaction between the evolution equation of the cross-covariance (shown in (48)) and the physical properties of the traffic model (reflected in (P.1)-(P.3)), we also derive the boundeness of the unobservable block of the Kalman gain. In summary, the combination of the update scheme of the KF and the intrinsic properties of the traffic model is critical in showing the boundedness of the Kalman gain under unobservable modes.

    In this subsection, we show that for an unobservable local section, the mean estimate of each cell will ultimately achieve the physically meaningful interval, thus the mean estimation error is also ultimately bounded. Unlike typical unobservable scenarios where the mean estimation error diverges (as shown in Example 3), the boundedness of the mean error here is ensured by the intrinsic physical properties of the traffic model, i.e., the relationship between the density and the sending/receiving capacity for each cell, as illustrated in the proof of the next proposition.

    Proposition 1. Consider an unobservable local section as shown in Figure 4 that stays inside an unobservable mode while k(kU0,). For all ϵ>0, a finite time t(ϵ) exists such that ˉρlk|k(ϵ,ϱm+ϵ) for all k>kU0+t(ϵ) and for all l{1,,n}, independent of the initial estimate. Moreover, the mean estimation error satisfies ˉηk|k<n(ϱm+ϵ) for all k>kU0+t(ϵ), independent of the initial estimate.

    Proof. Denote as ˉηbk|k=(ˉη1k|k,ˉηn1+n2k|k,ˉηnk|k) the mean error of the three boundary cells. Since the three boundary cells are all inside the observable subsystem, it follows that ˉηbk|k0 as k.

    The proof is by induction. In Step 1, we use an induction from cell 1 to the downstream cells to show that if the estimate of cell 1 converges to the true state, then the estimate of all cells will ultimately be greater than ϵ for all ϵ>0. In Step 2, we use an induction from the two downstream boundary cells (i.e., cell n1+n2 and cell n) to their upstream cells to show that if the estimates of the two downstream boundary cells converge to the true state, then the estimate of all cells will ultimately be smaller than ϱm+ϵ for all ϵ>0. In Step 3, we combine Step 1 and Step 2 to derive an ultimate bound for the mean estimation error.

    Step 1. We use induction to show that for all ϵ>0 and l{1,,n}, there exists a finite time tl1(ϵ) such that ˉρlk|k>ϵ for all k>kU0+tl1(ϵ).

    Since the upstream boundary cell (i.e., cell 1) is in the observable subsystem, we have ˉη1k|k0 and ˉρ1k|kρ1k, where ρ1k0. Hence a finite time t11(ϵ) exists such that ˉρ1k|k>ϵn for all k>kU0+t11(ϵ).

    For all interior cells on link 1, i.e., cells indexed by l{2,3,,n1}, suppose ˉρl1k|k>(l1)ϵn, if ˉρlk|k<(l1)ϵn, we obtain from (9) that

    f(ˉρl1k|k,ˉρlk|k)=vmˉρl1k|k>vm(l1)ϵn, (31)
    f(ˉρlk|k,ˉρl+1k|k)vmˉρlk|k. (32)

    It follows that the estimate of cell l satisfies

    ˉρlk+1|k+1=ˉρlk|k+ΔtΔx(f(ˉρl1k|k,ˉρlk|k)f(ˉρlk|k,ˉρl+1k|k))Kk+1(l,1)ˉη1k+1|kKk+1(l,2)ˉηn1+n2k+1|kKk+1(l,3)ˉηnk+1|k>ˉρlk|k+vmΔtΔx|ˉρlk|k+(l1)ϵn|k(ΓkU0|kU0)ˉηbk|k, (33)

    where the inequality is due to Kkk(ΓkU0|kU0) given in Lemma 3. Thus there exists a scalar v1>Δxk(ΓkU0|kU0)vmΔt such that

    ˉρlk+1|k+1ˉρlk|k>v0|ˉρlk|k+(l1)ϵn|,for all |ˉρlk|k+(l1)ϵn|v1ˉηbk|k (34)

    where v0=vmΔtΔxk(ΓkU0|kU0)v1>0. Also note that ˉηbk|k0 as k, which indicates that the one-step change of the estimates is ultimately positive, and large enough so that a finite time tl1(ϵ) exists such that ˉρlk|k>lϵn>ϵ for all k>kU0+tl1(ϵ) [21].

    We now show that for the two cells on the downstream side of the junction, i.e., cell n1+1 and cell n1+n2+1, there exist finite times tn1+11(ϵ) and tn1+n2+11(ϵ) such that ˉρn1+1k|k>(n1+1)ϵn>ϵ for all k>kU0+tn1+11(ϵ) and ˉρn1+n2+1k|k>(n1+1)ϵn>ϵ for all k>kU0+tn1+n2+11(ϵ). Suppose ˉρn1k|k>n1ϵn, if ˉρn1+1k|k<n1ϵn, the junction solver follows diverge case Ⅱ or diverge case Ⅲ. Hence, the flow from cell n1 to cell n1+1 satisfies:

    f(ˉρn1k|k,ˉρn1+1k|k)={1αd+1s(ˉρn1k|k)>vmn1ϵndiverge case IIs(ˉρn1k|k)r(ˉρn1+n2+1k|k)>vmn1ϵndiverge case III, 

    and the outgoing flow for cell n1+1 satisfies:

    f(ˉρn1+1k|k,ˉρn1+2k|k)vmˉρn1+1k|k.

    Following the similar arguments as in (33)-(34), it can be concluded that there exist a finite time tn1+11(ϵ) such that ˉρn1+1k|k>(n1+1)ϵn>ϵ for all k>kU0+tn1+11(ϵ). Applying the same analysis for cell n1+n2+1, it can be concluded that there exist a finite time tn1+n2+11(ϵ) such that ˉρn1+n2+1k|k>(n1+1)ϵn>ϵ for all k>kU0+tn1+n2+11(ϵ). Continuing the induction on link 2 from cell n1+1 to cell n1+n2, we obtain that for all ϵ>0 and l{n1+1,n1+2,,n1+n2}, there exists a finite time tl1(ϵ) such that ˉρlk|k>lϵn>ϵ for all k>kU0+tl1(ϵ). As for the cells on link 3, we process the same induction from cell n1+n2+1 to cell n, which yields that for all ϵ>0 and l{n1+n2+1,n1+n2+2,,n}, there exists a finite time tl1(ϵ) such that ˉρlk|k>(ln2)ϵn>ϵ for all k>kU0+tl1(ϵ).

    Let t1(ϵ)=maxl{1,,n}{tl1(ϵ)}, it is concluded that ˉρlk|k>ϵ for all k>kU0+t1(ϵ) and l{1,,n}. This proves the ultimate lower bound of the estimates.

    Step 2. We use induction to show that for all ϵ>0 and l{1,,n}, there exists a finite time tl2(ϵ) such that ˉρlk|k<ϱm+ϵ for all k>kU0+tl2(ϵ).

    Since the two downstream boundary cells (indexed by n1+n2 and n) are in the observable subsystem, we have ˉηn1+n2k|k0 and ˉρn1+n2k|kρn1+n2k, as well as ˉηnk|k0 and ˉρnk|kρnk. Given the facts that ρn1+n2kϱm and ρnkϱm, there exist finite times tn1+n22(ϵ) and tn2(ϵ) such that ˉρn1+n2k|k<ϱm+ϵn for all k>kU0+tn1+n22(ϵ), and ˉρnk|k<ϱm+ϵn for all k>kU0+tn2(ϵ).

    For all interior cells on link 3, i.e., cells indexed by l{n1+n2+1,n1+n2+2,,n1}, suppose ˉρl+1k|k<ϱm+(nl)ϵn, if ˉρlk|k>ϱm+(nl)ϵn, we obtain from (9) that

    f(ˉρl1k|k,ˉρlk|k)w(ϱmˉρlk|k), (35)
    f(ˉρlk|k,ˉρl+1k|k)=w(ϱmˉρl+1k|k)>w((nl)ϵn). (36)

    It follows that the estimate of cell l satisfies

    ˉρlk+1|k+1=ˉρlk|k+ΔtΔx(f(ˉρl1k|k,ˉρlk|k)f(ˉρlk|k,ˉρl+1k|k))Kk+1(l,1)ˉη1k+1|kKk+1(l,2)ˉηn1+n2k+1|kKk+1(l,3)ˉηnk+1|k<ˉρlk|kwΔtΔx|ˉρlk|kϱm(nl)ϵn|+k(ΓkU0|kU0)ˉηbk|k. (37)

    Thus there exists scalar w1 such that Δxk(ΓkU0|kU0)wΔt<w1, and

    ˉρlk+1|k+1ˉρlk|k<w0|ˉρlk|kϱm(nl)ϵn|,for all |ˉρlk|kϱm(nl)ϵn|w1ˉηbk|k. (38)

    Also note that ˉηbk|k0 as k, which indicates that the one-step change of the estimates is ultimately negative, and large enough so that a finite time tl2(ϵ) exists such that ˉρlk|k<ϱm+(nl+1)ϵn<ϱm+ϵ for all k>kU0+tl2(ϵ).

    The above arguments can be generalized for all cells on link 2. Hence for all ϵ>0 and l{n1+1,n1+2,,n1+n21}, there exists a finite time tl2(ϵ) such that ˉρlk|k<ϱm+(n1+n2l+1)ϵn<ϱm+ϵ for all k>kU0+tl2(ϵ).

    We now show that for the cell on the upstream side of the junction, i.e., cell n1, there exists finite time tn12(ϵ) such that ˉρn1k|k<ϱm+(nn1+1)ϵn<ϱm+ϵ for all k>kU0+tn12(ϵ). Suppose ˉρn1+1k|k<ϱm+n2ϵn and ˉρn1+n2+1k|k<ϱm+n3ϵn, if ˉρn1k|k>ϱm+(nn1)ϵn=ϱm+(n2+n3)ϵn, the incoming and outgoing flows of cell n1 satisfy

    f(ˉρn11k|k,ˉρn1k|k)w(ϱmˉρn1k|k),

    and

    f(ˉρn1k|k,ˉρn1+1k|k)+f(ˉρn1k|k,ˉρn1+n2+1k|k)={s(ˉρn1k|k)=qm>w(n2+n3nϵ)diverge case II or IIIr(ˉρn1+1k|k)+r(ˉρn1+n2+1k|k)>w(n2+n3nϵ)diverge case I.

    Following the similar arguments as in (37)-(38) it can be concluded that there exist finite time tn12(ϵ) such that ˉρn1k|k<ϱm+(nn1+1)ϵn<ϱm+ϵ for all k>kU0+tn12(ϵ). Continuing the induction from cell n1 to cell 1, it follows that for all l{1,2,,n1} there exists a finite time tl2(ϵ) such that ˉρlk|k<ϱm+(nl+1)ϵnϱm+ϵ for all k>kU0+tl2(ϵ).

    Let t2(ϵ)=maxl{1,,n}{tl2(ϵ)}, we obtain ˉρlk|k<ϱm+ϵ for all k>kU0+t2(ϵ) and l{1,,n}. This proves the ultimate upper bound of the estimates.

    Step 3. Combining Steps 1 and 2, and define t(ϵ)=maxl{t1(ϵ),t2(ϵ)}, we obtain ˉρlk|k(ϵ,ϱm+ϵ) for all l{1,,n} and k>kU0+t(ϵ). Consequently, ˉηk|k<n(ϱm+ϵ) for all k>kU0+t(ϵ).

    Proposition 1 indicates that when the mean estimation error of the three boundary cells converges to zero, it will drive the state estimate of all the interior cells inside [0,ϱm] due to the conservation law and the flow-density relationship embedded in the traffic model. For example, when the state estimate ˉρlk|k is smaller than zero, the sending capacity of cell l is much smaller than the receiving capacity of cell l (as shown in equations (31)-(32)). Consequently, the update equation of the estimate (33) ensures that the one-step change of the state estimate of cell l is always positive, and the magnitude of the one-step change is proportional to the distance between zero and the current state estimate ˉρlk|k. This ensures that the estimate of cell l is constantly pushed towards zero unless it is sufficiently close to zero. The ultimate upper bound can also be derived under the same fashion.

    In this article, we establish the theoretical performance of the KF applied to estimate the traffic density on transportation networks under unobservable scenarios. To facilitate the performance analysis of the KF, a linear SMM-J model is introduced which combines a junction solver with the switched linear system representation of the CTM. It is shown that in addition to the existence of shocks, the presence of junctions contributes significantly to the non-observability of the system.

    To derive the error bounds for the KF under unobservable traffic estimation problems, we analyze several properties of the state transition matrices of the SMM-J, which reflect the intrinsic physical properties (e.g., vehicle conservation and the CFL condition in the discretization scheme) of the traffic model. Based on the above properties of the SMM-J, we show that the infinity norm of the Kalman gain is uniformly bounded under unobservable modes. Finally, we show that the mean estimate of each cell is ultimately bounded inside the physically meaningful interval, provided that the density measurements of the boundary cells are available. The ultimate lower and upper bounds are derived based on the convergence (to zero) of the mean estimation error of the boundary cells, the boundedness of the Kalman gain, and the flow-density relationship embedded in the model prediction step of the KF. As indicated in the proof, feeding sensor data back to the estimator is critical to ensure physically meaningful estimates under unobservable system, which cannot be naturally achieved by an open-loop observer. These results provide some theoretical insights into the performance of sequential estimation algorithms widely used in traffic monitoring applications.

    Example 3. Consider a linear discrete system describing the evolution of a moving object. The state vector is constructed as ρk=(ρ1k,ρ2k,ρ3k) , where ρ1k|k , ρ2k|k , and ρ3k|k are the location, speed, and acceleration of the moving object at time kN , respectively. The moving object travels with a constant acceleration. The system dynamics is given by

    ρk+1=Akρk+ωk,ρkR3, (39)

    where ωkN(0,Qk) , the state transition matrix and the model error covariance matrices are given as follows:

    Ak=(110.5011001),Qk=(100010001),for all k.

    The initial state is ρ0=(2,1,0.05) . The sensor measures the acceleration of the moving object, i.e., the measurement is modeled by

    zk=Hkρk+vk,zkR, (40)

    where

    Hk=(001),vkN(0,Rk) with Rk=1,for all k.

    We use the KF (3)-(4) to estimate the state, where the initial condition is set to be ˉη0|0=(3,2,0.2) and Γ0|0=I3 .

    The system (39)-(40) is not observable, which can be concluded by computing its observability matrix [4,Theorem 6.O1], and showing that the observability matrix is not full rank. The mean estimation error evolves as the following equation:

    ˉηk|k=(IKkHk)Ak1ˉηk1|k1. (41)

    In Figure 5a, the solid curve shows the analytical evolution of ˉηk|k which follows (41). A Monte Carlo test of Nr=10,000 realizations of the KF is also conducted, and the dashed curve in Figure 5a shows the empirical evolution of the estimation error ˆηk|k , where ˆηk|k=1NrNrr=1ηr,k|k , and ηr,k|k is the posterior estimation error at time k on the rth realization. We also plot in Figure 5b the trace of the estimation error covariance tr(Γk|k) . It is shown that unlike the observable scenarios described in Lemma 1, the error covariance and the estimation error diverge as k increases in this example, which is typical for unobservable systems.

    Figure 5.  The evolutions of the estimation errors (A) and the trace of the error covariance (B) when using the KF to track the unobservable system (39)-(40).

    The proof is divided into two steps. In Step 1, we apply properties (P.1) and (P.2) to show that (27) holds for the modes where the junction solver follows diverge case Ⅰ or diverge case Ⅱ. In Step 2, properties (P.1) and (P.3) are applied to show that (27) holds for the modes where the junction solver follows diverge case Ⅲ.

    For all k0+1<kk1 and i,j{1,,n} , the (i,j)th entry of κ=kAκ is given by

    (κ=kAκ)(i,j)=nr=1((+1κ=kAκ)(i,r))(A(r,j)). (42)

    Step 1. Suppose Ak is under a mode where the junction solver follows diverge case Ⅰ or diverge case Ⅱ. Recall from (P.2) that

    nr=1Ak(r,j)1,for all k(k0,k1] and j{1,,n}.

    Hence, the (i,j)th entry of κ=kAκ is no greater than the convex combination of all the entries on the ith row of +1κ=kAκ . Moreover, recall from (P.1) that

    0Ak(r,c)1,for all k(k0,k1] and r,c{1,,n}

    it follows that

    0(κ=kAκ)(i,j)1,for all k(k0,k1][k0+1,k) and i,j{1,,n}

    thus (27) follows directly by setting =k0+1 in the above equation.

    Step 2. Suppose Ak is under a mode where the junction solver follows diverge case Ⅲ. We prove for the case where f(ρn1k,ρn1+1k)=r(ρn1+1k) , and the proof for the case where f(ρn1k,ρn1+1k)=s(ρn1k)r(ρn1+n2+1k) follows by symmetry.

    Recall from (P.3) that

    nr=1Ak(r,j)1,for all k(k0,k1] and j{j|j{1,,n},jn1+1}. (43)

    For j=n1+1 , the sum of all entries of Ak on column j is given by

    nr=1Ak(r,n1+1)=Ak(n1,n1+1)+Ak(n1+1,n1+1)+Ak(n1+n2+1,n1+1)=wΔtΔx+(1wΔtΔx)+wΔtΔx=1+wΔtΔx,for all k(k0,k1] .

    Additionally, one may note that for all k(k0,k1] ,

    Ak(r,n1+n2+1)={1if r=n1+n2+1 0otherwise.

    It follows that for all k0+1<kk1 ,

    (κ=kAκ)(r,n1+n2+1)={1if r=n1+n2+1 0otherwise. (44)

    Combining (43) and (44) with (42), we obtain that for all (i,j)(n1+n2+1,n1+1) , the (i,j)th entry of κ=kAκ is no greater than the convex combination of all the (non-zero) entries on the ith row of +1κ=kAκ . Also recall from (P.3) that for all k(k0,k1] ,

    Ak(r,c)=0,for all r{n1+1,,n} and c{1,n1}

    which yields that for all k0+1<kk1 ,

    (+1κ=kAκ)(r,c)=0,for all r{n1+1,,n} and c{1,n1}

    thus

    (+1κ=kAκ)(n1+n2+1,n1)=0,for all k0+1<kk1.

    Hence for (i,j)=(n1+n2+1,n1+1) , the (i,j)th entry of κ=kAκ is also no greater than the convex combination of all the (non-zero) entries on the ith row of +1κ=kAκ . Moreover, according to (P.1) it holds that

    0Ak(r,c)1,for all k(k0,k1] and r,c{1,,n}.

    It can be concluded that

    0(κ=kAκ)(i,j)1,for all k(k0,k1][k0+1,k) and i,j{1,,n}

    thus (27) follows directly by setting =k0+1 in the above equation.

    In an unobservable mode, the SMM-J can be transformed to the Kalman observability canonical form. The transformed state consists of the observable and the unobservable parts of the system, i.e.,

    ρ(t)k=Uρk=(ρ(1)kρ(2)k),

    where U is an orthogonal matrix, ρ(1)kRd1 and ρ(2)kRd2 are the state in the observable and unobservable subsystems, respectively, with d1+d2=n . Moreover, since the densities of the three boundary cells are directly measured, it holds that d13 . As a consequence, system (28)-(29) is transformed to the following formula:

    ρ(t)k+1=A(t)kρ(t)k+u(t)k+ω(t)k,ρkRn,zk=H(t)kρ(t)k+vk,zkR3,

    where the transformed state transition matrix A(t)k and the transformed observation matrix H(t)k can also be partitioned according to the observable and unobservable subsystems, i.e.,

    A(t)k=UAkU=(A(1)k0d1,d2A(21)kA(2)k),H(t)k=HkU=(H(1)k0), (45)

    with H(1)kR3×d1 defined as follows:

    H(1)k={I3if d1=3(I303,d13)if d1>3for all k.

    Moreover, the transformed system input is given by u(t)k=Uuk , and the transformed model noise is given by w(t)k=UwkN(0,Q(t)k) , where the transformed model error covariance Q(t)k can be partitioned to blocks corresponding to the observable and unobservable subsystems, i.e.,

    Q(t)k=UQkU=(Q(1)kQ(12)kQ(21)kQ(2)k).

    The prior estimation error covariance matrix partitioned into the observable and unobservable subsystems is constructed as follows:

    Γ(t)k|k1=(Γ(1)k|k1Γ(12)k|k1Γ(21)k|k1Γ(2)k|k1).

    In the KF, the prior error covariance matrix is computed recursively by the Riccati equation

    Γ(t)k+1|k=A(t)k(Γ(t)k|k1Γ(t)k|k1(H(t)k)(H(t)kΓ(t)k|k1(H(t)k)+Rk)1×H(t)kΓ(t)k|k1)(A(t)k)+Q(t)k, (46)

    Define

    Υ(1)k=A(1)kA(1)kΓ(1)k|k1(H(1)k)(H(t)kΓ(t)k|k1(H(t)k)+Rk)1H(1)k=A(1)kA(1)kK(1)kH(1)k,

    and apply partition into observable and unobservable subsystems to both sides of (46), we obtain the following two blocks of equations describing the evolutions of Γ(1)k+1|k and Γ(12)k+1|k :

    Γ(1)k+1|k=Υ(1)kΓ(1)k|k1(A(1)k)+Q(1)k, (47)
    Γ(12)k+1|k=Υ(1)kΓ(12)k|k1(A(2)k)+Υ(1)kΓ(1)k|k1(A(21)k)+Q(12)k. (48)

    In this section, we present the explicit formula of k(ΓkU0|kU0) and prove Lemma 3. As detailed in Appendix.3, we transform the state vector according to observable and unobservable subsystems, i.e.,

    ρ(t)k=Uρk=(ρ(1)kρ(2)k),

    where ρ(1)kRd1 and ρ(2)kRd2 are the state in the observable and unobservable subsystems, respectively. The transformed Kalman gain is given by

    K(t)k=UKk=(K(1)kK(21)k), (49)

    where K(1)k and K(21)k correspond to the observable and unobservable subsystems, respectively, with

    K(1)k=Γ(1)k|k1(H(1)k)(Rk+H(1)kΓ(1)k|k1(H(1)k))1, (50)
    K(21)k=Γ(21)k|k1(H(1)k)(Rk+H(1)kΓ(1)k|k1(H(1)k))1. (51)

    Appendix.4.1. Explicit formula of the Kalman gain bound. Define

    a1=maxk(kU0,kU1]{Ak}, a2=maxk(kU0,kU1]{Ak},

    and

    ˜a1=maxk(kU0,kU1]A(1)k,    ˜a2=maxk(kU0,kU1](A(1)k), ˜a3=maxk(kU0,kU1]σmax(A(1)k), ˜a4=maxk(kU0,kU1]A(21)k.

    Moreover, define as ˜c1 and ˜c2 the lower and upper bounds of the error covariance of the observable subsystem, i.e.,

    ˜c1I<Γ(1)k|k<˜c2I,for all k(kU0,kU1] (52)

    and let

    ˜c3=(˜c2+q11˜c22˜a3)1, ˜t=n2d1(ˇc2ˇc11)12, ˜q=(1˜c3˜c1)12˜p=d1˜c2˜a4(˜a1˜a2˜c2+q2)q11+q2, ˜γ=nnΓkU0|kU0(a1a2)2+nna1a2q2+nq2.

    The upper bound of Kk for k(kU0,kU1] in (30) is defined as

    k(ΓkU0|kU0)=3d1r1max{nd1(ΓkU0|kU0a1a2+q2),1d1(˜a1˜a2˜c2+q2),˜γ,˜t˜q˜γ+˜p,˜t˜p˜q1˜q+˜p}.

    Appendix.4.2. Proof of Lemma 3. The proof consists of the following five steps. Step 1 derives an upper bound for KkU0+1 . Step 2 derives an upper bound of K(1)k for k(kU0+1,kU1] . In Step 3, we study the convergence rate of the error dynamics of the observable subsystem, which is also related to the boundedness of K(21)k . Based on the convergence rate obtained in Step 3, Step 4 derives an upper bound of K(21)k for k(kU0+1,kU1] . Step 5 combines the above steps together and concludes the proof.

    Step 1. At time step kU0+1 , the Kalman gain is computed as follows:

    KkU0+1=ΓkU0+1|kU0HkU0+1(RkU0+1+HkU0+1ΓkU0+1|kU0HkU0+1)1,

    where ΓkU0+1|kU0=AkU0ΓkU0|kU0AkU0+QkU0 . Given that ΓkU0|kU0nΓkU0|kU0 , Qk<nq2 , and define

    a1=maxk(kU0,kU1]{Ak},a2=maxk(kU0,kU1]{Ak},

    the prior error covariance at time kU0+1 satisfies

    ΓkU0+1|kU0AkU0ΓkU0|kU0AkU0+QkU0<nΓkU0|kU0a1a2+nq2.

    Moreover, since

    (RkU0+1+HkU0+1ΓkU0+1|kU0HkU0+1)13(RkU0+1+HkU0+1ΓkU0+1|kU0HkU0+1)1=3(σmin(RkU0+1+HkU0+1ΓkU0+1|kU0HkU0+1))13(σmin(RkU0+1))1<3r1,

    it follows that

    KkU0+1ΓkU0+1|kU0HkU0+1(RkU0+1+HkU0+1ΓkU0+1|kU0HkU0+1)1<3nr1(ΓkU0|kU0a1a2+q2).

    Step 2. As stated in (50), Kalman gain associated with the observable subsystem is given by

    K(1)k=Γ(1)k|k1(H(1)k)(Rk+H(1)kΓ(1)k|k1(H(1)k))1.

    According to Lemma 1, there exist constants ˜c1 and ˜c2 such that the error covariance of the observable subsystem satisfies

    ˜c1I<Γ(1)k|k<˜c2I,for all k(kU0,kU1] . (53)

    Given that

    Γ(1)k|k1=A(1)kΓ(1)k1|k1(A(1)k)+Q(1)k1,

    we have

    Γ(1)k|k1˜a1˜a2Γ(1)k1|k1+Q(1)k1<d1(˜a1˜a2˜c2+q2),

    with ˜a1 and ˜a2 defined as

    ˜a1=maxk(kU0,kU1]A(1)k,˜a2=maxk(kU0,kU1](A(1)k).

    Following the similar argument as in Step 1, we obtain

    K(1)k<3d1r1(˜a1˜a2˜c2+q2),for all k(kU0+1,kU1] .

    Step 3. Define the Lyapunov function of the observable subsystem as

    V(1)k=(ˉη(1)k|k)(Γ(1)k|k)1ˉη(1)k|k.

    According to Lemma 3 in [31], the one-step change of V(1)k is given by:

    V(1)k+1V(1)k=(ˉη(1)k|k)(Γ(1)k|k+Γ(1)k|k(A(1)k)×(Q(1)k+Γ(1)k+1|k(H(1)k)R1k+1H(1)kΓ(1)k+1|k)1A(1)kΓ(1)k|k)1ˉη(1)k|kˉη(1)k|k2Γ(1)k|k+Γ(1)k|k(A(1)k)×(Q(1)k+Γ(1)k+1|k(H(1)k)R1k+1H(1)kΓ(1)k+1|k)1A(1)kΓ(1)k|k1,

    where

    Γ(1)k|k+Γ(1)k|k(A(1)k)(Q(1)k+Γ(1)k+1|k(H(1)k)R1k+1H(1)kΓ(1)k+1|k)1A(1)kΓ(1)k|k<˜c2+q11Γ(1)k|k(A(1)k)A(1)kΓ(1)k|k˜c2+q11Γ(1)k|k(A(1)k)A(1)kΓ(1)k|k<˜c2+q11˜c22˜a3,

    with ˜a3 defined as

    ˜a3=maxk(kU0,kU1]σmax(A(1)k),

    and σmax(M) is the maximum singular value of matrix M . It follows that for all k(kU0,kU1] , the Lyapunov function V(1)k satisfies

    ˜c12ˉη(1)k|k2<V(1)k<˜c11ˉη(1)k|k2,andV(1)k+1V(1)k<˜c3ˉη(1)k|k2,

    where

    ˜c3=˜c2+q11˜c22˜a3.

    Hence, for all k(kU0+1,kU1] , the 2-norm of the mean estimation error of the observable subsystem satisfies

    ˉη(1)k|k<(˜c2V(1)k)12<(˜c2V(1)kU0+1(1c3˜c1)kkU01)12<(˜c2˜c1ˉη(1)kU0+1|kU0+12(1˜c3˜c1)kkU01)12=(˜c2˜c1)12ˉη(1)kU0+1|kU0+1((1˜c3˜c1)12)kkU01. (54)

    Moreover, for all k(kU0+1,kU1] , the mean estimation error of the observable subsystem is given as follows:

    ˉη(1)k|k=kU0+2κ=kΥ(1)κˉη(1)kU0+1|kU0+1, (55)

    where Υ(1)κ=Γ(1)κ|κ(Γ(1)κ|κ1)1A(1)κ1 . Combining (54) and (55), it is concluded based on the definition of matrix induced norm that

    kU0+2κ=kΥ(1)κ(˜c2˜c1)12((1˜c3˜c1)12)kkU01,for k(kU0+1,kU1] . (56)

    Step 4. Vectorizing both sides of (48) yields that for k(kU0,kU1] ,

    vec{Γ(12)k+1|k}=(A(2)kΥ(1)k)vec{Γ(12)k|k1}+vec{Υ(1)kΓ(1)k|k1(A(21)k)}+vec{Q(12)k},

    which implies that for all k(kU0+1,kU1] ,

    vec{Γ(12)k+1|k}=(kU0+2κ=k(A(2)κΥ(1)κ))vec{Γ(12)kU0+2|kU0+1}+Φk, (57)

    where

    Φk=vec{Υ(1)kΓ(1)k|k1(A(21)k)+Q(12)k}+(A(2)kΥ(1)k)vec{Υ(1)k1Γ(1)k1|k2(A(21)k1)+Q(12)k1}+(A(2)kΥ(1)k)(A(2)k1Υ(1)k1)vec{Υ(1)k2Γ(1)k2|k3(A(21)k2)+Q(12)k2}++kU0+3κ=k(A(2)κΥ(1)κ)vec{Υ(1)kU0+2Γ(1)kU0+2|kU0+1(A(21)kU0+2)+Q(12)kU0+2}.

    The explicit form of A(2)kΥ(1)k reads

    A(2)kΥ(1)k=(A(2)k(1,1)Υ(1)kA(2)k(1,d2)Υ(1)kA(2)k(d2,1)Υ(1)kA(2)k(d2,d2)Υ(1)k),

    hence

    kU0+2κ=k(A(2)κΥ(1)κ)=(ϑk(1,1)kU0+2κ=kΥ(1)κϑk(1,d2)kU0+2κ=kΥ(1)κϑk(d2,1)kU0+2κ=kΥ(1)κϑk(d2,d2)kU0+2κ=kΥ(1)κ),

    where ϑk(i,j) is the (i,j)th element of kU0+2κ=kA(2)κ . Define

    P=(0d2,nd2Id2),

    and given that the top right block of A(t)k is a zero matrix 0d1,d2 (as shown in (45)), it can be concluded that

    kU0+2κ=kA(2)κ=P(kU0+2κ=kA(t)κ)P=P(kU0+2κ=kUAκU)P=PU(kU0+2κ=kAκ)UP. (58)

    Based on Lemma 2, the element of satisfies

    Hence, it can be derived from (58) that

    Consequently,

    (59)

    where the last inequality is due to (56). Recall from (53) that for . Since

    it follows that for all , and the prior error covariance of the observable subsystem satisfies for . As a consequence,

    (60)

    Define as

    it follows that6 for ,

    6Recall that for matrix , .

    (61)

    Substituting (59) and (61) into (57), we obtain that for ,

    where is either a non-increasing or a non-decreasing function of . Hence, we obtain that for ,

    where

    Also since

    it follows that for ,

    Step 5. Combining Steps 1, 2 and 4, it can be concluded that for

    which completes the proof.



    [1] Z. Zhang, P. Cui, W. Zhu, Deep Learning on Graphs: A Survey, IEEE Trans. Knowl. Data Eng., 34 (2022), 249–270. https://doi.org/10.1109/TKDE.2020.2981333 doi: 10.1109/TKDE.2020.2981333
    [2] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, P. Vandergheynst, The emerging field of signal processing on graphs: Extending high dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30 (2013), 83–98. https://doi.org/10.1109/MSP.2012.2235192 doi: 10.1109/MSP.2012.2235192
    [3] A. Sandryhaila, J. M. F. Moura, Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure, IEEE Signal Process. Mag., 31 (2014), 80–90. https://doi.org/10.1109/MSP.2014.2329213 doi: 10.1109/MSP.2014.2329213
    [4] A. Sandryhaila, J. M. F. Moura, Discrete signal processing on graphs, IEEE Trans. Signal Process., 61 (2013), 1644–1656. https://doi.org/10.1109/TSP.2013.2238935 doi: 10.1109/TSP.2013.2238935
    [5] J. Bruna, W. Zaremba, A. Szlam, Y. Lecun, Spectral networks and locally connected networks on graphs, arXiv preprint, (2013), arXiv: 1312.6203. https://doi.org/10.48550/arXiv.1312.6203
    [6] D. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, eet al., Convolutional networks on graphs for learning molecular fingerprints, Adv. Neural Inf. Process. Syst., 28 (2015), 2224–2232.
    [7] T. N. Kipf, M. Welling, Semi-supervised classification with graph convolutional networks, arXiv preprint, (2016), arXiv: 1609.02907.
    [8] J. Atwood, D. Towsley, Diffusion-convolutional neural networks, Adv. Neural Inf. Process. Syst., 29 (2016), 1993–2001.
    [9] M. Defferrard, X. Bresson, P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, Adv. Neural Inf. Process. Syst., 29 (2016), 3837–3845.
    [10] R. Levie, F. Monti, X. Bresson, M. M. Bronstein, CayleyNets: Graph convolutional neural networks with complex rational spectral filters, IEEE Trans. Signal Process., 67 (2019), 97–109. https://doi.org/10.1109/TSP.2018.2879624 doi: 10.1109/TSP.2018.2879624
    [11] R. Levie, W. Huang, L. Bucci, M. Bronstein, G. Kutyniok, Transferability of Spectral Graph Convolutional Neural Networks, J. Mach. Learn. Res., 22 (2021), 12462–112520.
    [12] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, M. M. Bronstein, Geometric deep learning on graphs and manifolds using mixture model CNNs, . IEEE Conf. Comput. Vis. Pattern Recognit., Honolulu, HI, USA, 2017, 5425–5434. https://doi.org/10.1109/CVPR.2017.576
    [13] M. Fey, J. E. Lenssen, F. Weichert, H. Müller, SplineCNN: fast geometric deep learning with continuous b-spline kernels, Proc. IEEE Conf. Comput. Vis. Pattern Recognit., (2018), 869–877. https://doi.org/10.1109/CVPR.2018.00097 doi: 10.1109/CVPR.2018.00097
    [14] W. L. Hamilton, Z. Ying, J. Leskovec, Inductive representation learning on large graphs, Adv. Neural Inf. Process. Syst., 30 (2017), 1024–1034.
    [15] Y. Zhao, J. Qi, Q. Liu, R. Zhang, WGCN: Graph Convolutional Networks with Weighted Structural Features, in 2021 SIGIR, (2021), 624–633. https://doi.org/10.1145/3404835.3462834
    [16] H. Wu, C. Wang, Y. Tyshetskiy, A. Docherty, K. Lu, L. Zhu, Adversarial examples for graph data: Deep insights into attack and defense, arXiv preprint, (2019), arXiv: 1903.01610. https://doi.org/10.48550/arXiv.1903.01610
    [17] D. Zügner, S. Günnemann, Adversarial attacks on graph neural networks via meta learning, arXiv preprint, (2019), arXiv: 1902.08412. https://doi.org/10.48550/arXiv.1902.08412
    [18] K. Xu, H. Chen, S. Liu, P. Chen, T. Weng, M. Hong, et al., Topology attack and defense for graph neural networks: An optimization perspective, in Proc. Int. Joint Conf. Artif. Intell., (2019), 3961–3967. https://doi.org/10.24963/ijcai.2019/550
    [19] L. Chen, J. Li, J. Peng, A survey of adversarial learning on graph, arXiv preprint, (2003), arXiv: 2003.05730. https://doi.org/10.48550/arXiv.2003.05730
    [20] L. Chen, J. Li, J. Peng, Y. Liu, Z. Zheng, C. Yang, Understanding Structural Vulnerability in Graph Convolutional Networks, in Proc. Int. Joint Conf. Artif. Intell., (2021), 2249–2255. https://doi.org/10.24963/ijcai.2021/310
    [21] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y. Bengio, Graph attention networks, arXiv preprint, (2017), arXiv: 1710.10903. https://doi.org/10.48550/arXiv.1710.10903
    [22] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit. L. Jones, A. N. Gomez, et al., Attention is all you need, Adv. Neural Inf. Process. Syst., 30 (2017), 5998–6008.
    [23] C. Zhuang, Q. Ma, Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification, in Proc. Int. Conf. World Wide Web, (2018), 499–508. https://doi.org/10.1145/3178876.3186116
    [24] F. Hu, Y. Zhu, S. Wu, L. Wang, T. Tan, Hierarchical Graph Convolutional Networks for Semi-supervised Node Classification, in Proc. Int. Joint Conf. Artif. Intell., (2019), 4532–4539. https://doi.org/10.24963/ijcai.2019/630
    [25] Y. Zhang, S. Pal, M. Coates, D. Ü stebay, Bayesian graph convolutional neural networks for semi-supervised classification, in Proc. Int. Joint Conf. Artif. Intell., 33 (2019), 5829–5836. https://doi.org/10.1609/aaai.v33i01.33015829
    [26] Y. Luo, R. Ji, T. Guan, J. Yu, P. Liu, Y. Yang, Every node counts: Self-ensembling graph convolutional networks for semi-supervised learning, Pattern Recognit., 106 (2020), 107451. https://doi.org/10.1016/j.patcog.2020.107451 doi: 10.1016/j.patcog.2020.107451
    [27] P. Gong, L. Ai, Neighborhood Adaptive Graph Convolutional Network for Node Classification, IEEE Access, 7 (2019), 170578–170588. https://doi.org/10.1109/ACCESS.2019.2955487 doi: 10.1109/ACCESS.2019.2955487
    [28] I. Chami, Z. Ying, C. Ré, J. Leskovec, Hyperbolic graph convolutional neural networks, in Proc. Adv. Neural Inf. Process. Syst., (2019), 4868–4879.
    [29] J. Dai, Y. Wu, Z. Gao, Y. Jia, A Hyperbolic-to-Hyperbolic Graph Convolutional Network, in 2021 IEEE/CVF Conf. Computer Vision Pattern Recogn. (CVPR), (2021), 154–163. https://doi.org/10.1109/CVPR46437.2021.00022
    [30] S. Rhee, S. Seo, S. Kim, Hybrid Approach of Relation Network and Localized Graph Convolutional Filtering for Breast Cancer Subtype Classification, in 2018 Int. Joint Conf. Artif. Intell., (2018), 3527–3534. https://doi.org/10.24963/ijcai.2018/490
    [31] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, G. E. Dahl, Neural Message Passing for Quantum Chemistry, in 2017 Int. Conf. Machine Learn., (2017), 1263–1272.
    [32] M. Zhang, Z. Cui, M. Neumann, Y. Chen, An End-to-End Deep Learning Architecture for Graph Classification, in Proc. Artif. Intell., (2018), 4438–4445. https://doi.org/10.1609/aaai.v32i1.11782
    [33] R. Ying, J. You, C. Morris, Hierarchical graph representation learning with differentiable pooling, in Proc. 32nd Int. Conf. Neural Inf. Process. Syst., (2018), 4805–4815.
    [34] Y. Ma, S. Wang, C. C Aggarwal, J. Tang, Graph convolutional networks with eigenpooling, in Proc. 25th ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., (2019), 723–731. https://doi.org/10.1145/3292500.3330982
    [35] J. Lee, I. Lee, J. Kang, Self-attention graph pooling, in Proc. 36th Int. Conf. Machine Learn., (2019), 3734–3743. Available from: http://proceedings.mlr.press/v97/lee19c/lee19c.pdf
    [36] C. Cangea, P. Velickovic, N. Jovanovic, T. Kipf, P. Lio, Towards sparse hierarchical graph classifiers, in Proc. Adv. Neural Inf. Process. Syst., (2018). https://doi.org/10.48550/arXiv.1811.01287
    [37] H. Gao, S. Ji, Graph U-Nets, in Proc. 36th Int. Conf. Machine Learn., (2019), 2083–2092. https://doi.org/10.1109/TPAMI.2021.3081010
    [38] H. Gao, Z. Wang, S. Ji, Large-Scale Learnable Graph Convolutional Networks, in Proc. Knowl. Disc. Data Min., (2018), 1416–1424. https://doi.org/10.1145/3219819.3219947
    [39] W. Chiang, X. Liu, S. Si, Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks, in Proc. Knowl. Disc. Data Min., (2019), 257–266. https://doi.org/10.1145/3292500.3330925
    [40] D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun, Q. Gu, Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks, in Proc. Adv. Neural Inf. Process. Syst., (2019), 11249–11259.
    [41] J. Wang, Y. Wang, Z. Yang, Bi-GCN: Binary Graph Convolutional Network, in 2021 IEEE/CVF Conf. Comput. Vision Pattern Recogn. (CVPR), (2021), 1561–1570. https://doi.org/10.1109/CVPR46437.2021.00161
    [42] F. Monti, K. Otness, M. M. Bronstein, MOTIFNET: A Motif-Based Graph Convolutional Network for Directed Graphs, in Proc. IEEE Data Sci. Workshop, (2018), 225–228. https://doi.org/10.1109/DSW.2018.8439897
    [43] J. Du, S. Zhang, G. Wu, J. M. F. Moura, S. Kar, Topology adaptive graph convolutional networks, arXiv preprint, (2017), arXiv: 1710.10370.
    [44] E. Yu, Y. Wang, Y. Fu, D. B. Chen, M. Xie, Identifying critical nodes in complex networks via graph convolutional networks, Knowl.-Based Syst., 198 (2020), 105893. https://doi.org/10.1016/j.knosys.2020.105893 doi: 10.1016/j.knosys.2020.105893
    [45] C. Li, X. Qin, X. Xu, D. Yang, G. Wei, Scalable Graph Convolutional Networks with Fast Localized Spectral Filter for Directed Graphs, IEEE Access, 8 (2020), 105634–105644. https://doi.org/10.1109/ACCESS.2020.2999520 doi: 10.1109/ACCESS.2020.2999520
    [46] S. Abu-El-Haija, A. Kapoor, B. Perozzi, J. Lee, N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification, in Proc. Conf. Uncertainty in Artif. Intell., (2019), 841–851.
    [47] S. Wan, C. Gong, P. Zhong, B. Du, L. Zhang, J. Yang, Multiscale Dynamic Graph Convolutional Network for Hyperspectral Image Classification, IEEE Trans. Geosci. Remote. Sens., 58 (2020), 3162–3177. https://doi.org/10.1109/TGRS.2019.2949180 doi: 10.1109/TGRS.2019.2949180
    [48] R. Liao, Z. Zhao, R. Urtasun, R. S. Zemel, LanczosNet: Multi-Scale Deep Graph Convolutional Networks, arXiv preprint., (2019), arXiv: 1901.01484. Available from: https://openreview.net/pdf?id = BkedznAqKQ
    [49] S. Luan, M. Zhao, X. Chang, D. Precup, Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks, in Proc. Conf. Workshop on Neural Inform. Process. Syst., 32 (2019), 10943–10953. Available from: https://proceedings.neurips.cc/paper_files/paper/2019/file/ccdf3864e2fa9089f9eca4fc7a48ea0a-Paper.pdf
    [50] F. Manessi, A. Rozza, M. Manzo, Dynamic Graph Convolutional Networks, Pattern Recogn., 97 (2020), 107000. https://doi.org/10.1016/j.patcog.2019.107000 doi: 10.1016/j.patcog.2019.107000
    [51] A. Pareja, G. Domeniconi, J. Chen, T. Ma, T. Suzumura, EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs, in Proc. Int. Joint Conf. Artif. Intell., (2020), 5363–5370. https://doi.org/10.1609/aaai.v34i04.5984
    [52] Z. Qiu, K. Qiu, J. Fu, D. Fu, DGCN: Dynamic Graph Convolutional Network for Efficient Multi-Person Pose Estimation, in Proc. Int. Joint Conf. Artif. Intell., (2020), 11924–11931. https://doi.org/10.1609/aaai.v34i07.6867
    [53] T. Song, Z. Cui, Y. Wang, W. Zheng, Q. Ji, Dynamic Probabilistic Graph Convolution for Facial Action Unit Intensity Estimation, in Proc. IEEE Conf. Comput. Vision Pattern Recogn., (2021), 4845–4854. https://doi.org/10.1109/CVPR46437.2021.00481
    [54] M. S. Schlichtkrull, T. N. Kipf, P. Bloem, R. Berg, I. Titov, M. Welling, Modeling Relational Data with Graph Convolutional Networks, In The Semantic Web: 15th Int. Conf., ESWC 2018, Heraklion, Crete, Greece, June 3–7, 2018, 593–607. https://doi.org/10.1007/978-3-319-93417-4_38
    [55] Z. Huang, X. Li, Y. Ye, M. K. Ng, MR-GCN: Multi-Relational Graph Convolutional Networks based on Generalized Tensor Product, in Proc. Int. Joint Conf. Artif. Intell., (2020), 1258–1264. https://doi.org/10.24963/ijcai.2020/175
    [56] J. Chen, L. Pan, Z. Wei, X. Wang, C. W. Ngo, T. S. Chua, Zero-Shot Ingredient Recognition by Multi-Relational Graph Convolutional Network, in Proc. Int. Joint Conf. Artif. Intell., 34 (2020), 10542–10550. https://doi.org/10.1609/aaai.v34i07.6626
    [57] P. Gopalan, S. Gerrish, M. Freedman, D. Blei, D. Mimno, Scalable inference of overlapping communities, in Proc. Conf. Workshop on Neural Inform. Process. Syst., (2012), 2249–2257.
    [58] R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Süsstrunk, SLIC superpixels compared to state-of-the-art superpixel methods, IEEE Trans. Pattern Anal. Mach. Intell., 34 (2012), 2274–2282. https://doi.org/10.1109/TPAMI.2012.120 doi: 10.1109/TPAMI.2012.120
    [59] W. Zheng, P. Jing, Q. Xu, Action Recognition Based on Spatial Temporal Graph Convolutional Networks, in Proc. 3rd Int. Conf. Comput. Sci. Appl. Eng., 118 (2019), 1–5. https://doi.org/10.1145/3331453.3361651
    [60] D. Tian, Z. Lu, X. Chen, L. Ma, An attentional spatial temporal graph convolutional network with co-occurrence feature learning for action recognition, Multimed. Tools Appl., 79 (2020), 12679–12697. https://doi.org/10.1007/s11042-020-08611-4 doi: 10.1007/s11042-020-08611-4
    [61] Y. Chen, G. Ma, C. Yuan, B. Li, H. Zhang, F. Wang, et al., Graph convolutional network with structure pooling and joint-wise channel attention for action recognition, Pattern Recogn., 103 (2020), 107321. https://doi.org/10.1016/j.patcog.2020.107321 doi: 10.1016/j.patcog.2020.107321
    [62] J. Dong, Y. Gao, H. J. Lee, H. Zhou, Y. Yao, Z. Fang, et al., Action Recognition Based on the Fusion of Graph Convolutional Networks with High Order Features, Appl. Sci., 10 (2020), 1482. https://doi.org/10.3390/app10041482 doi: 10.3390/app10041482
    [63] Z. Chen, S. Li, B. Yang, Q. Li, H. Liu, Multi-Scale Spatial Temporal Graph Convolutional Network for Skeleton-Based Action Recognition, in Proc. Int. Joint Conf. Artif. Intell., 35 (2021), 1113–1122. https://doi.org/10.1609/aaai.v35i2.16197
    [64] Y. Bin, Z. Chen, X. Wei, X. Chen, C. Gao, N. Sang, Structure-aware human pose estimation with graph convolutional networks, Pattern Recogn., 106 (2020), 107410. https://doi.org/10.1016/j.patcog.2020.107410 doi: 10.1016/j.patcog.2020.107410
    [65] R. Wang, C. Huang, X. Wang, Global Relation Reasoning Graph Convolutional Networks for Human Pose Estimation, IEEE Access, 8 (2020), 38472–38480. https://doi.org/10.1109/ACCESS.2020.2973039 doi: 10.1109/ACCESS.2020.2973039
    [66] T. Sofianos, A. Sampieri, L. Franco, F. Galasso, Space-Time-Separable Graph Convolutional Network for Pose Forecasting, in Proc. IEEE/ICCV Int. Conf. Comput. Vision, (2021), 11209–11218. https://doi.org/10.48550/arXiv.2110.04573
    [67] Z. Zou, W. Tang, Modulated Graph Convolutional Network for 3D Human Pose Estimation, in Proc. ICCV, (2021), 11457–11467. https://doi.org/10.1109/ICCV48922.2021.01128
    [68] B. Yu, H. Yin, Z. Zhu, Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting, in Proc. Int. Joint Conf. Artif. Intell., (2018), 3634–3640. https://doi.org/10.24963/ijcai.2018/505
    [69] Y. Han, S. Wang, Y. Ren, C. Wang, P. Gao, G. Chen, Predicting Station-Level Short-Term Passenger Flow in a Citywide Metro Network Using Spatiotemporal Graph Convolutional Neural Networks, ISPRS Int. J. Geo-Inform., 8 (2019), 243. https://doi.org/10.3390/ijgi8060243 doi: 10.3390/ijgi8060243
    [70] B. Zhao, X. Gao, J. Liu, J. Zhao, C. Xu, Spatiotemporal Data Fusion in Graph Convolutional Networks for Traffic Prediction, IEEE Access, 8 (2020), 76632–76641. https://doi.org/10.1109/ACCESS.2020.2989443 doi: 10.1109/ACCESS.2020.2989443
    [71] L. Ge, H. Li, J. Liu, A. Zhou, Temporal Graph Convolutional Networks for Traffic Speed Prediction Considering External Factors, in Proc. Int. Conf. Mobile Data Manag., (2019), 234–242. https://doi.org/10.1109/MDM.2019.00-52
    [72] L. Ge, S. Li, Y. Wang, F. Chang, K. Wu, Global Spatial-Temporal Graph Convolutional Network for Urban Traffic Speed Prediction, Appl. Sci.-basel, 10 (2020), 1509. https://doi.org/10.3390/app10041509 doi: 10.3390/app10041509
    [73] P. Han, P. Yang, P. Zhao, S. Shang, Y. Liu, J. Zhou, et al., GCN-MF: Disease-Gene Association Identification by Graph Convolutional Networks and Matrix Factorization, Knowl. Disc. Data Min., (2019), 705–713. https://doi.org/10.1145/3292500.3330912 doi: 10.1145/3292500.3330912
    [74] J. Li, Z. Li, R. Nie, Z. You, W. Bao, FCGCNMDA: predicting miRNA-disease associations by applying fully connected graph convolutional networks, Mol. Genet. Genom., 295 (2020), 1197–1209. https://doi.org/10.1007/s00438-020-01693-7 doi: 10.1007/s00438-020-01693-7
    [75] L. Wang, Z. You, Y. Li, K. Zhang, Y. Huang, GCNCDA: A new method for predicting circRNA-disease associations based on Graph Convolutional Network Algorithm, PLoS Comput. Biol., 16 (2020), e1007568. https://doi.org/10.1371/journal.pcbi.1007568 doi: 10.1371/journal.pcbi.1007568
    [76] C. Wang, J. Guo, N. Zhao, Y. Liu, X. Liu, G. Liu, et al., A Cancer Survival Prediction Method Based on Graph Convolutional Network, IEEE Trans. NanoBiosci., 19 (2019), 117–126. https://doi.org/10.1109/TNB.2019.2936398 doi: 10.1109/TNB.2019.2936398
    [77] H. Chen, F. Zhuang, L. Xiao, L. Ma, H. Liu, R. Zhang, et al., AMA-GCN: Adaptive Multi-layer Aggregation Graph Convolutional Network for Disease Prediction, in Proc. IJCAI, (2021), 2235–2241. https://doi.org/10.24963/ijcai.2021/308
    [78] K. Gopinath, C. Desrosiers, H. Lombaert, Learnable Pooling in Graph Convolutional Networks for Brain Surface Analysis, IEEE Trans. Pattern Anal. Mach. Intell., 44 (2022), 864–876. https://doi.org/10.1109/TPAMI.2020.3028391 doi: 10.1109/TPAMI.2020.3028391
    [79] R. Ying, R. He, K. Chen, Graph Convolutional Neural Networks for Web-Scale Recommender Systems, in Proc. Knowl. Disc. Data Min., (2018), 974–983. https://doi.org/10.1145/3219819.3219890
    [80] X. Xia, H. Yin, J. Yu, Q. Wang, L. Cui, X. Zhang, Self-Supervised Hypergraph Convolutional Networks for Session-based Recommendation, in Proc. Int. Joint Conf. Artif. Intell., 35 (2021), 4503–4511. https://doi.org/10.1609/aaai.v35i5.16578
    [81] H. Chen, L. Wang, Y. Lin, C. Yeh, F. Wang, H. Yang, Structured Graph Convolutional Networks with Stochastic Masks for Recommender Systems, in Proc. SIGIR, (2021), 614–623. https://doi.org/10.1145/3404835.3462868
    [82] L. Chen, Y. Xie, Z. Zheng, H. Zheng, J. Xie, Friend Recommendation Based on Multi-Social Graph Convolutional Network, IEEE Access, 8 (2020), 43618–43629. https://doi.org/10.1109/ACCESS.2020.2977407 doi: 10.1109/ACCESS.2020.2977407
    [83] T. Zhong, S. Zhang, F. Zhou, K. Zhang, G. Trajcevski, J. Wu, Hybrid graph convolutional networks with multi-head attention for location recommendation, World Wide Web, 23 (2020), 3125–33151. https://doi.org/10.1007/s11280-020-00824-9 doi: 10.1007/s11280-020-00824-9
    [84] T. H. Nguyen, R. Grishman, Graph Convolutional Networks with Argument-Aware Pooling for Event Detection, in Proc. AAAI Confer. Artif. Intell., 32 (2018). https://doi.org/10.1609/aaai.v32i1.12039
    [85] Z. Guo, Y. Zhang, W. Lu, Attention Guided Graph Convolutional Networks for Relation Extraction, Ann. Meet. Assoc. Comput. Linguist., (2019), 241–251. https://doi.org/10.18653/v1/P19-1024 doi: 10.18653/v1/P19-1024
    [86] Y. Hong, Y. Liu, S. Yang, K. Zhang, A. Wen, J. Hu, Improving Graph Convolutional Networks Based on Relation-Aware Attention for End-to-End Relation Extraction, IEEE Access, 8 (2020), 51315–51323. https://doi.org/10.1109/ACCESS.2020.2980859 doi: 10.1109/ACCESS.2020.2980859
    [87] Z. Meng, S. Tian, L. Yu, Y. Lv, Joint extraction of entities and relations based on character graph convolutional network and Multi-Head Self-Attention Mechanism, J. Exp. Theor. Artif. Intell., 33 (2021), 349–362. https://doi.org/10.1080/0952813X.2020.1744198 doi: 10.1080/0952813X.2020.1744198
    [88] L. Yao, C. Mao, Y. Luo, Graph Convolutional Networks for Text Classification, Artif. Intell., (2019), 7370–7377. https://doi.org/10.1609/aaai.v33i01.33017370 doi: 10.1609/aaai.v33i01.33017370
    [89] M. Chandra, D. Ganguly, P. Mitra, B. Pal, J. Thomas, NIP-GCN: An Augmented Graph Convolutional Network with Node Interaction Patterns, in Proc. SIGIR, (2021), 2242–2246. https://doi.org/10.1145/3404835.3463082
    [90] L. Xiao, X. Hu, Y. Chen, Y. Xue, D. Gu, B. Chen, et al., Targeted Sentiment Classification Based on Attentional Encoding and Graph Convolutional Networks, Appl. Sci., 10 (2020), 957. https://doi.org/10.3390/app10030957 doi: 10.3390/app10030957
    [91] P. Zhao, L. Hou, O. Wu, Modeling sentiment dependencies with graph convolutional networks for aspect-level sentiment classification, Knowl.-Based Syst., 193 (2020), 105443. https://doi.org/10.1016/j.knosys.2019.105443 doi: 10.1016/j.knosys.2019.105443
    [92] S. Jiang, Q. Chen, X. Liu, B. Hu, L. Zhang, Multi-hop Graph Convolutional Network with High-order Chebyshev Approximation for Text Reasoning, arXiv preprint, (2021), arXiv: 2106.05221. https://doi.org/10.18653/v1/2021.acl-long.513
    [93] R. Li, H. Chen, F. Feng, Z. Ma, X. Wang, E. Hovy, Dual Graph Convolutional Networks for Aspect-based Sentiment Analysis, in Proc. 59 Ann. Meet. Assoc. Comput. Linguist. And 11th Int. joint Conf. Nat. Language process., 1 (2021), 6319–6329.
    [94] L. Lv, J. Cheng, N. Peng, M. Fan, D. Zhao, J. Zhang, Auto-encoder based Graph Convolutional Networks for Online Financial Anti-fraud, IEEE Comput. Intell. Financ. Eng. Econ., (2019), 1–6. https://doi.org/10.1109/CIFEr.2019.8759109 doi: 10.1109/CIFEr.2019.8759109
    [95] C. Li, D. Goldwasser, Encoding Social Information with Graph Convolutional Networks for Political Perspective Detection in News Media, in Proc. 57th Ann. Meet. Assoc. Comput. Linguist., (2019), 2594–2604. https://doi.org/10.18653/v1/p19-1247
    [96] Y. Sun, T. He, J. Hu, H. Hang, B. Chen, Socially-Aware Graph Convolutional Network for Human Trajectory Prediction, in 2019 IEEE 3rd Inf. Technol. Network. Electron. Autom. Control Conf. (ITNEC), (2019), 325–333. https://doi.org/10.1109/ITNEC.2019.8729387
    [97] J. Chen, J. Li, M. Ahmed, J. Pang, M. Lu, X. Sun, Next Location Prediction with a Graph Convolutional Network Based on a Seq2seq Framework, KSII Trans. Internet Inf. Syst., 14 (2020), 1909–1928. https://doi.org/10.3837/tiis.2020.05.003 doi: 10.3837/tiis.2020.05.003
    [98] X. Li, Y. Xin, C. Zhao, Y. Yang, Y. Chen, Graph Convolutional Networks for Privacy Metrics in Online Social Networks, Appl. Sci.-Basel, 10 (2020), 1327. https://doi.org/10.3390/app10041327 doi: 10.3390/app10041327
  • This article has been cited by:

    1. Yanbing Wang, Daniel B. Work, Estimation for heterogeneous traffic using enhanced particle filters, 2022, 18, 2324-9935, 568, 10.1080/23249935.2021.1881186
    2. Zlatinka Dimitrova, Flows of Substances in Networks and Network Channels: Selected Results and Applications, 2022, 24, 1099-4300, 1485, 10.3390/e24101485
    3. M. L. Delle Monache, J. Sprinkle, R. Vasudevan, D. Work, 2019, Autonomous vehicles: From vehicular control to traffic contro, 978-1-7281-1398-2, 4680, 10.1109/CDC40024.2019.9029535
    4. Yanbing Wang, Daniel B. Work, 2019, Heterogeneous traffic estimation with particle filtering, 978-1-5386-7024-8, 2551, 10.1109/ITSC.2019.8917248
    5. Joel C. de Goma, Lourd Andre B. Ammuyutan, Hans Luigi S. Capulong, Katherine P. Naranjo, Madhavi Devaraj, 2019, Vehicular Obstruction Detection In The Zebra Lane Using Computer Vision, 978-1-7281-0851-3, 362, 10.1109/IEA.2019.8715022
    6. Maria Laura Delle Monache, Sean T. McQuade, Hossein Nick Zinat Matin, Derek A. Gloudemans, Yanbing Wang, George L. Gunter, Alexandre M. Bayen, Jonathan W. Lee, Benedetto Piccoli, Benjamin Seibold, Jonathan M. Sprinkle, Daniel B. Work, Modeling, Monitoring, and Controlling Road Traffic Using Vehicles to Sense and Act, 2025, 8, 2573-5144, 211, 10.1146/annurev-control-030123-015145
  • Reader Comments
  • © 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(4710) PDF downloads(478) Cited by(20)

Figures and Tables

Figures(14)  /  Tables(7)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog