
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
[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 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, ρk∈Rn, | (1) |
zk=Hkρk+vk, zk∈Rm, | (2) |
where
Prediction:{ρk|k−1=Ak−1ρk−1|k−1+ukΓk|k−1=Ak−1Γk−1|k−1A⊤k−1+Qk−1, | (3) |
Correction:{ρk|k=ρk|k−1+Kk(zk−Hkρk|k−1)Γk|k=Γk|k−1−KkHkΓk|k−1Kk=Γk|k−1H⊤k(Rk+HkΓk|k−1H⊤k)−1. | (4) |
In (4), the matrix
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
αIn<Ik,k−N<βIn, for all k≥N, | (5) |
where
Ik1,k0=k1∑k=k0Ξ⊤k,k1H⊤kR−1kHkΞk,k1, |
where
Ξk,k1=k1−1∏κ=kA−1κ, and Ξk1,k=Ξ−1k,k1=k∏κ=k1−1Aκ. | (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
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
(C.2): the initial error covariance is positive definite, i.e.,
(C.3): the state transition matrix
then there exist positive constants
c1In<Γk|k<c2In, for all k≥0. |
Moreover, there exists positive constants
2For the remainder of this article, we denote as
‖ˉηk|k‖<aqk‖ˉη0|0‖, for all k≥0. |
When system (1)-(2) is not observable, the mean estimation error
The classical conservation law describing the evolution of traffic density
∂tρ+∂xF(ρ)=0. | (7) |
The function
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
ρlk+1=ρlk+ΔtΔx(f(ρl−1k,ρlk)−f(ρlk,ρl+1k)), | (8) |
where
f(ρl−1k,ρlk)=min{s(ρl−1k),r(ρlk)}. | (9) |
In (9),
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
F(ρ)={ρvmif ρ∈[0,ϱc]w(ϱm−ρ)if ρ∈[ϱc,ϱm], | (10) |
where
s(ρ)={ρvmif ρ∈[0,ϱc]qmif ρ∈[ϱc,ϱm] r(ρ)={qmif ρ∈[0,ϱc]w(ϱm−ρ)if ρ∈[ϱc,ϱm], | (11) |
where
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
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
(R.3): The distribution of flux
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)=(1−λ)(f1+f2)−λ(f2−αdf1)2, |
where
3One possible choice of
f(ρlk,ρik), f(ρlk,ρjk) = argmaxf1,f2 J(f1,f2)s.t. f1≤r(ρik) | (12) |
f2≤r(ρjk) | (13) |
f1+f2≤s(ρ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
According to the convex program in Definition 1, to obtain
● 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
● Conditioned on prioritizing maximizing the throughput, the point is as close as possible to the black dotted line (with slope
As shown in Figure 3, there are in total three scenarios depending on the values of
Under diverge case Ⅰ, the fluxes
f(ρlk,ρik)=r(ρik), f(ρlk,ρjk)=r(ρjk). | (15) |
Under diverge case Ⅱ, the fluxes
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)=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
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
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
(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
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.
Mode | F/C |
Transition |
Diverge case | Obser-vability |
|||||
near junction |
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 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. |
In the SMM-J, the density update scheme for the interior cells in each link (i.e., cells indexed by
ρ1k+1=ρ1k+ΔtΔx(ϕ1k−f(ρ1k,ρ2k)),ρn1+n2k+1=ρn1+n2k+ΔtΔx(f(ρn1+n2−1k,ρn1+n2k)−ϕ2k),ρnk+1=ρnk+ΔtΔx(f(ρn−1k,ρnk)−ϕ3k), |
where
ρn1k+1=ρn1k+ΔtΔx(f(ρn1−1k,ρ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
When applying the triangular fundamental diagram (10) to compute the flow across the cells, the traffic state
ρk+1=Akρk+Bρk1ϱm+Bqk1qm+Bϕkϕk, | (19) |
where
The next two examples demonstrate the construction of matrices
Θp(i,j)={1−vmΔtΔxif i=jvmΔtΔxif i=j+10otherwise, | (20) |
Δp(i,j)={1−wΔtΔxif i=jwΔtΔxif i=j−10otherwise. | (21) |
For
Ep3,p4p1,p2(i,j)={1if i=p3 and j=p40otherwise. | (22) |
Moreover, define
˜Θp={(Θp−10p−1,1vmΔtΔxE1,p−11,p−11)if p≥2, 1if p=1, |
and
˜Δp={(1wΔtΔxE1,11,p−10p−1,1Δp−1)if p≥2, 1if 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
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=(Θ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,3−En1+n2,2n,3−En,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
˜l1={l1if the shock has positive velocity or is stationaryl1−1if the shock has negative velocity, |
and
ˆl1=n1−1−˜l1, |
which are later used to simplify the notations to define matrices
˜l2=l2−n1, ˆl2=n2−˜l2, ˜l3=l3−n1−n2, ˆl3=n3−˜l3. |
At the junction, the sending capacity of cell
1. Diverge case Ⅰ: when
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=(Θ˜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,n−En1,n1+n2+1n,n+El2,l2n,n+El3,l3n,n),Bqk=ΔtΔx(−El2.l2n,n+El2+1,l2n,n−El3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3−En1+n2,2n,3−En,3n,3). |
2. Diverge case Ⅱ: when
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=(Θ˜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,n−En1+1,n1+2n,n+El2,l2n,n−En1+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,n−El2,l2n,n+El2+1,l2n,n−El3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3−En1+n2,2n,3−En,3n,3). |
3. Diverge case Ⅲ: when
f(ρn1k,ρn1+1k)=r(ρn1+1k)=w(ϱm−ρn1+1k),f(ρn1k,ρn1+n2+1k)=s(ρn1k)−r(ρn1+1k)=qm−w(ϱm−ρn1+1k), | (24) |
or obtained from (18), i.e.,
f(ρn1k,ρn1+1k)=s(ρn1k)−r(ρn1+n2+1k)=qm−w(ϱ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=(Θ˜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,n−En1+n2+1,n1+n2+2n,n−En1+n2+1,n1+1n,n+El3,l3n,n),Bqk=ΔtΔx(−El2.l2n,n+El2+1,l2n,n+En1+n2+1,n1+1n,n−El3,l3n,n+El3+1,l3n,n),Bϕk=ΔtΔx(E1,1n,3−En1+n2,2n,3−En,3n,3). |
Some properties of the state transition matrix
(P.1): For
0≤Ak(r,c)≤1,for all k∈N and r,c∈{1,⋯,n}. |
This property is due to the CFL condition [33] in the discretization scheme (8).
(P.2): When
n∑r=1Ak(r,c)≤1,for all k∈N 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
n∑r=1Ak(r,c)≤1,for all k∈N and c∈{c|c∈{1,⋯,n},c≠ℓ}, |
where
Ak(r,c)=0,for all k, r∈{n1+1,⋯,n} and c∈{1,⋯n1}. |
This is due to the facts that (i) the flows from cell
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
4Recall that the time instant
Ξk+1,k0+1=k0+1∏κ=kAκ, for k∈(k0,k1]. | (26) |
The
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.,
Incorporating model noise in the SMM-J (19) yields:
ρk+1=Akρk+uk+ωk, ρk∈Rn, | (28) |
where
uk=Bρk1ϱm+Bqk1qm+Bϕkϕk. |
The sensor measurements are modeled as follows:
zk=Hkρk+vk, zk∈R3, | (29) |
where the observation matrix
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
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
Lemma 3. Consider an unobservable local section shown in Figure 4. The local section stays inside an unobservable mode of the SMM-J while
5Recall that for matrix
‖Kk‖∞≤k(ΓkU0|kU0),for all k∈(kU0,kU1], | (30) |
where
Proof. The explicit formula of
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
Proof. Denote as
The proof is by induction. In Step 1, we use an induction from cell
Step 1. We use induction to show that for all
Since the upstream boundary cell (i.e., cell
For all interior cells on link 1, i.e., cells indexed by
f(ˉρl−1k|k,ˉρlk|k)=vmˉρl−1k|k>−vm(l−1)ϵn, | (31) |
f(ˉρlk|k,ˉρl+1k|k)≤vmˉρlk|k. | (32) |
It follows that the estimate of cell
ˉρlk+1|k+1=ˉρlk|k+ΔtΔx(f(ˉρl−1k|k,ˉρlk|k)−f(ˉρlk|k,ˉρl+1k|k))−Kk+1(l,1)ˉη1k+1|k−Kk+1(l,2)ˉηn1+n2k+1|k−Kk+1(l,3)ˉηnk+1|k>ˉρlk|k+vmΔtΔx|ˉρlk|k+(l−1)ϵn|−k(ΓkU0|kU0)‖ˉηbk|k‖∞, | (33) |
where the inequality is due to
ˉρlk+1|k+1−ˉρlk|k>v0|ˉρlk|k+(l−1)ϵn|,for all |ˉρlk|k+(l−1)ϵn|≥v1‖ˉηbk|k‖∞, | (34) |
where
We now show that for the two cells on the downstream side of the junction, i.e., cell
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
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
Let
Step 2. We use induction to show that for all
Since the two downstream boundary cells (indexed by
For all interior cells on link 3, i.e., cells indexed by
f(ˉρl−1k|k,ˉρlk|k)≤w(ϱm−ˉρlk|k), | (35) |
f(ˉρlk|k,ˉρl+1k|k)=w(ϱm−ˉρl+1k|k)>w(−(n−l)ϵn). | (36) |
It follows that the estimate of cell
ˉρlk+1|k+1=ˉρlk|k+ΔtΔx(f(ˉρl−1k|k,ˉρlk|k)−f(ˉρlk|k,ˉρl+1k|k))−Kk+1(l,1)ˉη1k+1|k−Kk+1(l,2)ˉηn1+n2k+1|k−Kk+1(l,3)ˉηnk+1|k<ˉρlk|k−wΔtΔx|ˉρlk|k−ϱm−(n−l)ϵn|+k(ΓkU0|kU0)‖ˉηbk|k‖∞. | (37) |
Thus there exists scalar
ˉρlk+1|k+1−ˉρlk|k<−w0|ˉρlk|k−ϱm−(n−l)ϵn|,for all |ˉρlk|k−ϱm−(n−l)ϵn|≥w1‖ˉηbk|k‖∞. | (38) |
Also note that
The above arguments can be generalized for all cells on link 2. Hence for all
We now show that for the cell on the upstream side of the junction, i.e., cell
f(ˉρn1−1k|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
Let
Step 3. Combining Steps 1 and 2, and define
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
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+1=Akρk+ωk,ρk∈R3, | (39) |
where
Ak=(110.5011001),Qk=(100010001),for all k. |
The initial state is
zk=Hkρk+vk,zk∈R, | (40) |
where
Hk=(001),vk∼N(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
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=(I−KkHk)Ak−1ˉηk−1|k−1. | (41) |
In Figure 5a, the solid curve shows the analytical evolution of
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
(ℓ∏κ=kAκ)(i,j)=n∑r=1((ℓ+1∏κ=kAκ)(i,r))(Aℓ(r,j)). | (42) |
Step 1. Suppose
n∑r=1Ak(r,j)≤1,for all k∈(k0,k1] and j∈{1,⋯,n}. |
Hence, the
0≤Ak(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
Step 2. Suppose
Recall from (P.3) that
n∑r=1Ak(r,j)≤1,for all k∈(k0,k1] and j∈{j|j∈{1,⋯,n},j≠n1+1}. | (43) |
For
n∑r=1Ak(r,n1+1)=Ak(n1,n1+1)+Ak(n1+1,n1+1)+Ak(n1+n2+1,n1+1)=wΔtΔx+(1−wΔtΔx)+wΔtΔx=1+wΔtΔx,for all k∈(k0,k1] . |
Additionally, one may note that for all
Ak(r,n1+n2+1)={1if r=n1+n2+1 0otherwise. |
It follows that for all
(ℓ∏κ=kAκ)(r,n1+n2+1)={1if r=n1+n2+1 0otherwise. | (44) |
Combining (43) and (44) with (42), we obtain that for all
Ak(r,c)=0,for all r∈{n1+1,⋯,n} and c∈{1,⋯n1}, |
which yields that for all
(ℓ+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≤ℓ<k≤k1. |
Hence for
0≤Ak(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
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
ρ(t)k+1=A(t)kρ(t)k+u(t)k+ω(t)k,ρk∈Rn,zk=H(t)kρ(t)k+vk,zk∈R3, |
where the transformed state transition matrix
A(t)k=UAkU⊤=(A(1)k0d1,d2A(21)kA(2)k),H(t)k=HkU⊤=(H(1)k0), | (45) |
with
H(1)k={I3if d1=3(I303,d1−3)if d1>3, for all k. |
Moreover, the transformed system input is given by
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|k−1=(Γ(1)k|k−1Γ(12)k|k−1Γ(21)k|k−1Γ(2)k|k−1). |
In the KF, the prior error covariance matrix is computed recursively by the Riccati equation
Γ(t)k+1|k=A(t)k(Γ(t)k|k−1−Γ(t)k|k−1(H(t)k)⊤(H(t)kΓ(t)k|k−1(H(t)k)⊤+Rk)−1×H(t)kΓ(t)k|k−1)(A(t)k)⊤+Q(t)k, | (46) |
Define
Υ(1)k=A(1)k−A(1)kΓ(1)k|k−1(H(1)k)⊤(H(t)kΓ(t)k|k−1(H(t)k)⊤+Rk)−1H(1)k=A(1)k−A(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=Υ(1)kΓ(1)k|k−1(A(1)k)⊤+Q(1)k, | (47) |
Γ(12)k+1|k=Υ(1)kΓ(12)k|k−1(A(2)k)⊤+Υ(1)kΓ(1)k|k−1(A(21)k)⊤+Q(12)k. | (48) |
In this section, we present the explicit formula of
ρ(t)k=Uρk=(ρ(1)kρ(2)k), |
where
K(t)k=UKk=(K(1)kK(21)k), | (49) |
where
K(1)k=Γ(1)k|k−1(H(1)k)⊤(Rk+H(1)kΓ(1)k|k−1(H(1)k)⊤)−1, | (50) |
K(21)k=Γ(21)k|k−1(H(1)k)⊤(Rk+H(1)kΓ(1)k|k−1(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]{‖A⊤k‖∞}, |
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
˜c1I<Γ(1)k|k<˜c2I,for all k∈(kU0,kU1], | (52) |
and let
˜c3=(˜c2+q−11˜c22˜a3)−1, ˜t=n2√d1(ˇc2ˇc−11)12, ˜q=(1−˜c3˜c1)12˜p=d1˜c2˜a4(˜a1˜a2˜c2+q2)q−11+q2, ˜γ=n√n‖ΓkU0|kU0‖(a1a2)2+n√na1a2q2+√nq2. |
The upper bound of
k(ΓkU0|kU0)=√3d1r1max{√nd1(‖ΓkU0|kU0‖a1a2+q2),1√d1(˜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
Step 1. At time step
KkU0+1=ΓkU0+1|kU0H⊤kU0+1(RkU0+1+HkU0+1ΓkU0+1|kU0H⊤kU0+1)−1, |
where
a1=maxk∈(kU0,kU1]{‖Ak‖∞},a2=maxk∈(kU0,kU1]{‖A⊤k‖∞}, |
the prior error covariance at time
‖ΓkU0+1|kU0‖∞≤‖AkU0‖∞‖ΓkU0|kU0‖∞‖A⊤kU0‖∞+‖QkU0‖∞<√n‖ΓkU0|kU0‖a1a2+√nq2. |
Moreover, since
‖(RkU0+1+HkU0+1ΓkU0+1|kU0H⊤kU0+1)−1‖∞≤√3‖(RkU0+1+HkU0+1ΓkU0+1|kU0H⊤kU0+1)−1‖=√3(σmin(RkU0+1+HkU0+1ΓkU0+1|kU0H⊤kU0+1))−1≤√3(σmin(RkU0+1))−1<√3r1, |
it follows that
‖KkU0+1‖∞≤‖ΓkU0+1|kU0‖∞‖H⊤kU0+1‖∞‖(RkU0+1+HkU0+1ΓkU0+1|kU0H⊤kU0+1)−1‖∞<√3nr1(‖ΓkU0|kU0‖a1a2+q2). |
Step 2. As stated in (50), Kalman gain associated with the observable subsystem is given by
K(1)k=Γ(1)k|k−1(H(1)k)⊤(Rk+H(1)kΓ(1)k|k−1(H(1)k)⊤)−1. |
According to Lemma 1, there exist constants
˜c1I<Γ(1)k|k<˜c2I,for all k∈(kU0,kU1] . | (53) |
Given that
Γ(1)k|k−1=A(1)kΓ(1)k−1|k−1(A(1)k)⊤+Q(1)k−1, |
we have
‖Γ(1)k|k−1‖∞≤˜a1˜a2‖Γ(1)k−1|k−1‖∞+‖Q(1)k−1‖∞<√d1(˜a1˜a2˜c2+q2), |
with
˜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+1−V(1)k=−(ˉη(1)k|k)⊤(Γ(1)k|k+Γ(1)k|k(A(1)k)⊤×(Q(1)k+Γ(1)k+1|k(H(1)k)⊤R−1k+1H(1)kΓ(1)k+1|k)−1A(1)kΓ(1)k|k)−1ˉη(1)k|k≤−‖ˉη(1)k|k‖2‖Γ(1)k|k+Γ(1)k|k(A(1)k)⊤×(Q(1)k+Γ(1)k+1|k(H(1)k)⊤R−1k+1H(1)kΓ(1)k+1|k)−1A(1)kΓ(1)k|k‖−1, |
where
‖Γ(1)k|k+Γ(1)k|k(A(1)k)⊤(Q(1)k+Γ(1)k+1|k(H(1)k)⊤R−1k+1H(1)kΓ(1)k+1|k)−1A(1)kΓ(1)k|k‖<˜c2+q−11‖Γ(1)k|k(A(1)k)⊤A(1)kΓ(1)k|k‖≤˜c2+q−11‖Γ(1)k|k‖‖(A(1)k)⊤A(1)k‖‖Γ(1)k|k‖<˜c2+q−11˜c22˜a3, |
with
˜a3=maxk∈(kU0,kU1]σmax(A(1)k), |
and
˜c−12‖ˉη(1)k|k‖2<V(1)k<˜c−11‖ˉη(1)k|k‖2,andV(1)k+1−V(1)k<−˜c3‖ˉη(1)k|k‖2, |
where
˜c3=˜c2+q−11˜c22˜a3. |
Hence, for all
‖ˉη(1)k|k‖<(˜c2V(1)k)12<(˜c2V(1)kU0+1(1−c3˜c1)k−kU0−1)12<(˜c2˜c1‖ˉη(1)kU0+1|kU0+1‖2(1−˜c3˜c1)k−kU0−1)12=(˜c2˜c1)12‖ˉη(1)kU0+1|kU0+1‖((1−˜c3˜c1)12)k−kU0−1. | (54) |
Moreover, for all
ˉη(1)k|k=kU0+2∏κ=kΥ(1)κˉη(1)kU0+1|kU0+1, | (55) |
where
‖kU0+2∏κ=kΥ(1)κ‖≤(˜c2˜c1)12((1−˜c3˜c1)12)k−kU0−1,for k∈(kU0+1,kU1] . | (56) |
Step 4. Vectorizing both sides of (48) yields that for
vec{Γ(12)k+1|k}=(A(2)k⊗Υ(1)k)vec{Γ(12)k|k−1}+vec{Υ(1)kΓ(1)k|k−1(A(21)k)⊤}+vec{Q(12)k}, |
which implies that for all
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|k−1(A(21)k)⊤+Q(12)k}+(A(2)k⊗Υ(1)k)vec{Υ(1)k−1Γ(1)k−1|k−2(A(21)k−1)⊤+Q(12)k−1}+(A(2)k⊗Υ(1)k)(A(2)k−1⊗Υ(1)k−1)vec{Υ(1)k−2Γ(1)k−2|k−3(A(21)k−2)⊤+Q(12)k−2}+⋯+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=(A(2)k(1,1)Υ(1)k⋯A(2)k(1,d2)Υ(1)k⋮⋱⋮A(2)k(d2,1)Υ(1)k⋯A(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
P=(0d2,n−d2Id2), |
and given that the top right block of
kU0+2∏κ=kA(2)κ=P(kU0+2∏κ=kA(t)κ)P⊤=P(kU0+2∏κ=kUAκU⊤)P⊤=PU(kU0+2∏κ=kAκ)U⊤P⊤. | (58) |
Based on Lemma 2, the
0≤(kU0+2∏κ=kAκ)(i,j)≤1,for all i,j∈{1,⋯,n} . |
Hence, it can be derived from (58) that
‖kU0+2∏κ=kˇA(2)κ‖∞≤‖kU0+2∏κ=kˇAκ‖∞≤‖U(kU0+2∏κ=kAκ)UT‖∞≤√n‖kU0+2∏κ=kAκ‖≤n2. |
Consequently,
‖kU0+2∏κ=k(A(2)κ⊗Υ(1)κ)‖∞≤n2‖kU0+2∏κ=kΥ(1)κ‖∞≤n2√d1(˜c2˜c1)12((1−˜c3˜c1)12)k−kU0−1=˜t˜qk−kU0−1, | (59) |
where the last inequality is due to (56). Recall from (53) that
Γ(1)k|k−1=A(1)kΓ(1)k−1|k−1(A(1)k)⊤+Q(1)k−1, |
it follows that
‖Υ(1)k‖∞≤√d1‖Γ(1)k|k(Γ(1)k|k−1)−1‖<√d1˜c2q−11,for k∈(kU0,kU1] . | (60) |
Define
˜a4=maxk∈(kU0,kU1]‖A(21)k‖∞, |
it follows that6 for
6Recall that for matrix
‖vec{Υ(1)kΓ(1)k|k−1(A(21)k)⊤}+vec{Q(12)k}‖∞≤‖Υ(1)kΓ(1)k|k−1(A(21)k)⊤‖∞+‖Q(12)k‖max<√d1˜c2q−11˜a4‖Γ(1)k|k−1‖∞+q2<d1˜c2˜a4(˜a1˜a2˜c2+q2)q−11+q2=˜p. | (61) |
Substituting (59) and (61) into (57), we obtain that for
‖vec{Γ(12)k+1|k}‖∞≤b(k)≜ |
where
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
![]() |
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 |
Mode | F/C |
Transition |
Diverge case | Obser-vability |
|||||
near junction |
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 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. |
Mode | F/C |
Transition |
Diverge case | Obser-vability |
|||||
near junction |
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 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. |