Combining Physics and Machine Learning for Network Flow Estimation
Authors: Arlei Lopes da Silva
Furkan Kocayusufoglu
Saber Jafarpour
Francesco Bullo
Ananthram Swami
Ambuj Singh
Venue: ICLR 2021 Poster (2021)
Keywords: graphs
networks
bilevel optimization
metalearning
flow graphs

Abstract: The flow estimation problem consists of predicting missing edge flows in a network (e.g., traffic, power, and water) based on partial observations. These missing flows depend both on the underlying \textit{physics} (edge features and a flow conservation law) as well as the observed edge flows. This paper introduces an optimization framework for computing missing edge flows and solves the problem using bilevel optimization and deep learning. More specifically, we learn regularizers that depend on edge features (e.g., number of lanes in a road, the resistance of a power line) using neural networks. Empirical results show that our method accurately predicts missing flows, outperforming the best baseline, and is able to capture relevant physical properties in traffic and power networks.

Published as a conference paper at ICLR 2021
COMBINING PHYSICS AND MACHINE LEARNING FOR NETWORK FLOW ESTIMATION
Arlei Silva, Furkan Kocayusufoglu
Computer Science Department, UC Santa Barbara, CA 93106-5110, USA
Saber Jafarpour, Francesco Bullo
Mechanical Engineering Department and the Center of Control, Dynamical Systems and Computation, UC Santa Barbara, CA 93 93106-5070, USA
Ananthram Swami
U.S. Army Research Lab, Adelphi, MD 20783, USA
Ambuj Singh
Computer Science Department, UC Santa Barbara, CA 93106-5110, USA
ABSTRACT
The flow estimation problem consists predicting missing edge flows in a net- work (e.g., traffic, power, and water) based on partial observations. These missing flows depend both on the underlying physics (edge features and a flow conser- vation law) well the observed edge flows. This paper introduces mization framework for computing missing edge flows and solves the problem using bilevel optimization and deep learning. More specifically, we learn regu- larizers that depend on edge features (e.g., number of lanes in a road, resistance of power line) using neural networks. Empirical results show that our method accurately predicts missing flows, outperforming the best baseline, and is able to capture relevant physical properties in traffic and power networks.
opti-
INTRODUCTION
In many applications, ranging from road traffic to supply chains to power networks, the dynamics of flows on edges of graph is governed by physical laws/models (Bressan et al., 2014, Garavello & Piecoli (006)_ For instance, the LWR model describes equilibrium equations for road traffic Lighthill & Whitham [1955); Richards (1956). However, it is often difficult to fully observe flows result, they rely off-the-shelf machine learning models to make predictions about missing flows (Li et al. 2017 Yu et al., 2018). A key limitation of these machine learning models is that they disregard the physics governing the flows. So. the question arises: can we combine physics and machine learning to make better flow predictions?
these applications and,
This paper investigates the problem of predicting missing edge flows based on partial observations and the underlying domain-spectin physics defined by flow conservation and edge features (Jia et al., 2019.. Edge flows depend on the graph topology due to a flow conservation law the total flow at every vertex is approximately its total out-flow. Moreover, the flow at edge also depends on its features, which might regularize the space of possible flow distributions in the graph. Here, propose model that learns how to predict missing flows from data using bilevel optimization (Franceschi et al. 2017) and neural networks. More specifically, features are given as inputs to a neural network that produces edge flow regularizers. Weights of the network are then optimized via reverse-mode differentiation based on a flow estimation loss from multiple train-validation pairs.
Our work falls under broader effort towards incorporating physics knowledge machine learning, which is relevant for natural sciences and engineering applications where data availability is lim- ited (Rackauckas et al. 2020 Conservation laws (of energy, mass, momentum, charge, etc.)

---

Published as a conference paper at ICLR 2021
essential to understanding of the physical world. The classical Noether's theorem shows that such laws arise from symmetries in nature (Hanc et al. 2004). However, flow estimation, which is an inverse problem (aranttlaa 2005 Arridge et al.] 2019), is ill-posed under conservation alone. Regularization enables us to apply domain-knowledge in the solution of inverse problems.
We motivate problem and evaluate its solutions using application scenarios. The first is road traffic networks (Coclite et al.) 2005). where vertices represent locations, edges are road segments, flows are counts of vehicles that traverse segment and features include numbers of lanes and speed limits. The second scenario is electric power networks (Dörfler et al., 2018), where vertices represent power buses, edges are power lines, flows are amounts of power transmitted and edge features include resistances and lengths of lines. Irrigation channels, gas pipelines, blood circulation, supply chains, air traffic, and telecommunication networks are other examples of flow graphs.
Our contributions can be summarized as follows: (1) We introduce missing flow estimation prob- lem with applications in broad class of flow graphs; (2) we propose a model for flow estimation that is able to learn the physics of flows by combining reverse-mode differentiation and neural networks; (3) we show that our model outperforms the best baseline by up to 18%; and (4) we provide evi- dence that our model learns interpretable physical properties, such as the role played by resistance in power transmission network and by the number lanes in a road traffic network.
FLOW ESTIMATION PROBLEM
We introduce the flow estimation problem, which consists of inferring missing flows in a network based on flow conservation law and edge features. We provide list of symbols in the Appendix.
Flow Graph. Let G(V, E, X)) be flow graph with vertices V (n (n=IV)), edges (m= [E), and edge feature matrix X' E IRnxd, where [ec are the features of edge e. A flow vector f E R contains the (possibly noisy) flow fe for each edge e E E. case G is directed, f RT, otherwise, a flow is negative if it goes against the arbitrary orientation of its edge. We assume that flows are induced by the graph, and thus, the total now-ingp plus out at each vertex is approximately conserved:
Σ ((Vru))
Σ (M.R))EE
f(ueo)), Vu E V
(Bi.u)ES
In the case of a road network, flow conservation implies that vehicles mostly remain on the road.
Flow Estimation Problem. Given graph G(V, E() with partial flow observations f E Rmm for subset 8' C E of edges (fe is the flow for E E', m'=1=" m). predict flows for edges in E E'.
In our road network example, partial vehicle counts f might be measured by sensors placed a few segments, and the goal is to estimate counts at the remaining segments. One would expect flows not to be fully conserved in most applications due to the existence of inputs and outputs, such as parking lots and power generators/consumer.. In case these input and output values are known exactly, they can be easily incorporated to our problem as flow observations. Moreover, they are known approximately, we can apply them as priors (as will be detailed in the next section). For the remain- ing of this paper, we assume that inputs and outputs are unknown and employ flow conservation as an approximation of the system. Thus, different from classical flow optimization problems, such as min-cost flow (Ahuja et al. 1988), we assume that flows are conserved approximately.
Notice that problem is similar the studied in Jia al. (209).. However, while their definition also assumes flow conservation, it does not take into account edge features. We claim that these features play important role in capturing the physics of flows. Our main contribution is new model that is able to learn how to regularize flows based on edge features using neural networks.
3 OUR APPROACH: PHYSICS+LEARNIVG
In this section, we introduce our approach for the flow estimation problem, which summarized in Figure I We formulate flow estimation as optimization problem (Section 3.I). where the interplay between the flow network topology and edge features is defined by the physics of flow graphs. Flow estimation is shown to be equivalent regularized least-squares problem (Section
2

---

Published as a conference paper at ICLR 2021
Flow graph
Edge regularizers
R-fold cross validation
Flow estimation loss
Sec. 3-
fold
B
Sec, 3.3
Edgee featurees
Edge Regularizer Que
Sec. 3.1. 3.2
ang BHx BFil + ||x x (
Flow estimation
Neural network with
(conservation regularizaioon)
paramelers +
Observed
Missing ..... Validation
Predicted flow
Figure 1: Summary the proposed approach for predicting missing flows in a graph based on partial observations and edge features. We learn to combine features and flow conservation law, which together define the physics of the flow graph. A regularization function Q(x'; +) modeled as neural network with parameters O takes input edge features X Xee] A flow estimation algorithm applies the regularization, partial observations (f), prior flows (x (0) and flow conservation to predict missing flows x. Network parameters @ are learned based on K K-fold cross validation loss with respect to validation flows & Our model trained end-to-end using reverse-men mode differentiation.
3.2, Moreover, we describe how the effect of edge features and the graph topology can be learned from data using bilevel optimization and neural networks in Section 3.3 Finally, we propose a reverse-mode differentiation algorithm for flow estimation in Section 3.4
3.1 FLOW ESTIMATION VIA OPTIMIZATION
The extent to which flow conservation holds for flows in graph is known as divergence and can be measured using the oriented incidence matrix B E R=xm of G. The matrix is defined as follows, B, = 1 if Eu such that ej (V;, u) E &, B,₃ = -1 if Bu such that ej (u, us) E E, and B, = 0, otherwise. Given B and f, the divergence at vertex u can be computed as:
(Bf),.
Σ S(V...)) (N.N)E
Σ (M.V))EE
S(u,v))
(1)
And thus, we can compute the total (squared) divergence in the graph as BB BT (B)))( One could try to solve the flow estimation problem by minimizing B while keeping the observed flows fixed, however, this problem ill-posed-there might be multiple solu- tions to the optimization. The standard approach in such a scenario is to resort to regularization. In particular, we apply generic regularization function & with parameters & as follows:
f* = arg min Bf 1 + 2f; +) st. fe = E
(2)
fen
where Ω is the domain of f, f()) R. is prior for flows, fe (fa) are entries of f (f) for edge and the constraint guarantees that observed flows not changed. Priors f()), not be confused with observed flows f, should be set according to the application (c.g., zero, based on a black- box model or historical data). Regarding the domain Ω we consider Ω R and Ω = Ry. The second case is relevant for directed graphs- when flows must follow edge orientations (e.g., traffic).
In et al. 20119) the authors set &f X, ()) f for regularization parameter X, which implies a uniform zero prior with an L2 penalty over edges. We claim that the regularization function plays important role in capturing the physics of flow graphs. As example, for a power network, should account for the resistance of the lines. Thus, we propose learning the regularization from data. Our approach is based least-squares formulation, which will be described next.
3

---

Published as a conference paper at ICLR 2021
3.2 REGULARIZED LEAST-SQUARES FORMULATION
Flow estimation problem can be viewed as an inverse problem (Taantola, 2005 Let x E Rm-m' be the vector of missing flows and E R= be a matrix such that Hi = if f maps to Ty (i.e., they associated to the same edge), and H O, otherwise. Moreover, let f R be such that fc = fe if e E and J. = O, otherwise. Using this notation, we define flow estimation as BHx = - Bf + e, where BH is forward operator, projecting x to a vector of vertex divergences, and - Bf + c is the observed data, capturing (negative) vertex divergences for observed flows. The error e can be interpreted as noise in observations or some level of model misspecification.
We can also define a regularized least-squares problem with the goal of recovering missing flows x:
arg min || + Bf 12 + ||x x (0) (2(x))))
XEI!'
where S2 is a projection of the domain of f to the space of ||x| xTMx is the matrix- scaled norm of and x()) Rm-m' priors for missing flows. The regularization function (f,, X;; f()) ②) has the form ||- x 1I ()) where the matrix ((x;)) θ) is function of param- eters and edge features X' We foeus on the case where Q(X; θ) is non-negative and diagonal.
Equation has Bayesian interpretation, with x being a maximum likelihood estimate under Gaussian assumption i.c. N Nxx(()) ((x:0)=1) and Bf I), (Tarantola 2005). Thus, 2(X;0) captures the variance in flow observations f in prior estimates f()) compared to the one. This allows the regularization function to adapt to different edges based on their features. For in- stance, in our road network example, Q(x: θ) might place a lower weight on flow conservation for flows at a road segment with a small number of lanes, which are possible traffic bottlenecks.
Given the least-squares formulation described in this section, how do we model the regularization function Q and learn its parameters Q? We would like Q to be expressive enough to be able to capture complex physical properties of flows, while è to computed accurately and efficiently. We will address these challenges in the remaining of this paper.
3.3 BILEVEL. OPTIMIZATION FOR META-IFFARNIG THE PHYSICS OF FL.WWS
This section introduces a model for flow estimation that is able to learn the regularization function Q(X:; θ) in Equation from data using bilevel optimization and neural networks.
Bilevel formulation. We learn the parameters & that determine the regularization function Q(X:; θ) using the following bilevel optimization formulation:
O arg min
E & x" x11
(4)
st. x arg min || + 2 x xollxxx0)
(5)
xEi
where the inner (lower) problem is the same as Equation B and the outer (upper) problem is the expected loss with respect to ground truth flows x-which estimate using cross-validation.
Notice that optimal values for parameters θ and missing flows x are both unknown the bilevel optimization problem. The expectation in Equation F is a function of multiple instances of the inner problem (Equation 5). Each inner problem instance has an optimal solution x" that depends on pa- rameters O In general, bilevel optimization is not only non-convex but also NP-hard (Colson al.) 2007). However, recent gradient- based solutions for bilevel optimization have been successfully ap- plied to large-scale problems, such syper-parameter optimization and meta-learning (Franceschil et al. 2018: Lorraine et al. 2020). We will first describe how we model the function Q(2;; +) and then discuss how this problem can be solved efficiently using reverse-mode differentiation.
We propose to model ((X;; θ) using neural network, where X' are inputs, O are learnable weights and the outputs are diagonal entries of the regularization matrix. This is a natural choice due the expressive power of neural nets (Cybenko 1989. Xu et al. 2018).
Multi-Layer Perceptron (MLP). An MLP-based @(X; θ) has the following form: ((x; θ) diag( (MP(((
4

---

Published as a conference paper at ICLR 2021
where ML Rm-m', For instance, Q(2:; @) can be a 2-layer MLP:
2(x,0) = =dig(a((%
(7)
where - (Wa), W wa) E Rdxh, W(2) R the number of nodes the hidden layer, both and are activation functions, and the bias was omitted for convenience.
Graph Neural Network (GNN). The MLP-based approach assumes that each entry [Q(X": +)),,e associated to an edge is function of its features X(e] only. However, are also interested in how entries [2 +)]e.e might depend on the features of neighborhood of e in the flow graph topology. Thus, consider the case where (x); θ) is GNN, which is described in the Appendix.
3.4 FLOw ESTIMATION ALGORITHM
We now focus on how to solve our bilevel optimization problem (Equations and 5). Our solution applies gradient-ban
approaches (c.g., SGD (Bottou & Bousquet 2008), Adam (Kingma & Ba 2014j) and, for simplicity, our description will be based on the particular case of Gradient Descent and assume a zero prior (x(") = 0). A key challenge in our problem is to efficiently approximate the gradient of the outer objective with respect the parameters O, which, by the chain rule, depends on the gradient of the inner objective with respect to θ.
We first introduce extra notation to describe the outer problem (Equation 4). Let (fi, gix) be one of K train-vale validation folds, both containing ground ground-truth flow values, such that fy IP and gi R2, For each fold k, we apply the inner problem (Equation to estimate missing flows Xx. Estimates for all folds concatenated into single vector x ;xx] and the same for validation sets g [g g2: g We define matrix R E Rex(m-m') such that Raj 1 if prediction zy corresponds to validation flow J: and Raj = 0, otherwise. Using this representation, we can approximate the expectation in the outer objective as (x +) = (1/K) - gl. where x depends implicitly on O We also introduce (x) the inner problem objective. Moreover, let r (Xx,j-1, O;-1) be one step of gradient descent for the value of x at iteration with learning rate 3:
T5(XaJj11 O;-1) X - 8V (x(a))
-
- 2.3 BJ (BH Bíx) + 2Qux6s-1]
where HR. Qk and fr. are the matrix H, sub-matrix of Q(2;; and the observed flows vector (see Section 3.2 for the specific fold We have assumed the domain (S²' of flows Xg.j to be the set of real vectors. For non-negative flows, we add the appropriate proximal operator to [-
Our algorithm applies Reverse-Mode Differentiation (RMD) (Domke 2012: Franceschi et al. 2017) to estimate V and optimizes θ also using iterative algorithm. The main idea of RMD is first unroll and store a finite number of iterations for the inner problem X1, X2,... .., and then reverse over those iterations estimate V V. which is computed follows:
or ax, O.)
or (x O.)
V (x,, Vx,,,((x,,0) V
(x)
θ2) Σ
II
ox,-1
00
particular, our reverse iteration based on following equations:
Vx (x,, 02) = (2/K)RT g)
or, (x,-1, O.) B 22(x;;,))
0x,-1
or (xJ-1, Q4) --4800/2;
d0
where (x(;; 0,0 is the gradient of the regularization function Q(X: O) evaluated θ, In our case, this gradient the same as the neural network gradients and is omitted here for convenience. Algorithm [ describes RMD approach for flow estimation. It receives inputs the flow net- work g(V, 8, X), K train-validation folds ((fe, &x) { and also hyperparameters T, J. a, and 3,
5

---

Published as a conference paper at ICLR 2021
Algorithm RMD Algorithm for Flow Estimation
Require: Flow network (VV, &, 2),, train-validation folds (fex (x) Bx))k= number of outer iterations
T and inner iterations J, learning rates a and 3
Ensure: Regularization parameters θ
Initialize parameters O
2: g <- gi....gh:
3: <- incidence matrix of g
4: for outer iterations L,... T do
5: Initialize missing flows X1,0 for all
6: for inner iterations j = 1....JJ do
7: for folds k = -1,... do
8: Xk.j f XR.j-1 28 [ B Bfa) + 2Q xM. end for
9:
10:
X, f [i.j xK,]
end for
12:
2J + (2/K) 1 8)
13:
for reverse inner iterations j 1,... do
- 4,2 (000) ( Zj + 1-2++1 2T 0(x:0
14:
16: end for
Update O; - 11-1- -
18:
end for
19: return parameters i
corresponding to the number of outer and inner iterations, and learning rates for the outer and inner problem, respectively. Its output is vector of optimal parameters θ for the regularization function Q(X; @) according to the bilevel objective Equations and 5 We use & to indicate our estimate of Ve (O,)) Iterations of the inner problem are stored for each train-validation fold in lines 4-12.
Reverse steps, which produce an estimate θ are performed in lines 13-17. We then use θ to update estimate of θ in line 17. The time and space complexities of the algorithm are O Km) and (JJ),, respectively, due to the cost of computing and storing the inner problem iterations.
As discussed in the previous section, bilevel optimization is non-convex and thus cannot guar- antee that Algorithm D will return a global optima. In particular, the learning objective our regularization function (x:: @) is non-convex-it is neural network. However, the inner problem (Equation 55) in our formulation has a convex objective (least-squares). In |Franceschi et al. (2018), the authors have shown that this property implies convergence. We also find that our algorithm often converges to a good estimate of the parameters in our experiments.
4 EXPERIMENTS
We evaluate our approaches for the flow estimation problem using two real datasets and a represen- tative set of baselines and metrics. Due to space limitations, we provide an extended version of this section, with more details on datasets, experimental settings, and additional results in the Appendix.
4.1 DATASETS
This section summarizes the datasets used in our evaluation. We normalize flow values to [0, 1] and map discrete features to real vector dimensions using one-hot encoding.
Vertices represent locations and directed edges represent road segments between two lo- cations in Los Angeles County, CA. Flows are daily average vehicle counts measured by sensors placed along highways the year 2018. We assign each sensor to an edge in the graph based on proximity and other sensor attributes. Our road network covers the Los Angeles County 5, 749 vertices, 7, 498 edges, of which 2, 879 edges (38% have sensors. The following features were mapped to 18-dimensional vector; lat-long coordinates, number of lanes, max-speed, and
Traffic:
with

---

Published as a conference paper at ICLR 2021
highway type (motorway, motorway link, trunk, etc.), in-degree, out-degree, and centrality (PageR- ank). The in-degree and centrality of an edge are computed based on its source vertex. Similarly, the out-degree of an edge is the out-degree of its target vertex.
Power: Vertices represent buses in Europe, undirected edges are power transmission lines and edge flows measure the total active power (in MW) being transmitted through the lines. The dataset is obtained from PyPSA-Euu (Hörsch et al. 2018 Brown et al. 2017) an optimization model of the European power transmission system-whie generates realistic power flows based on solutions of optimal linear power flow problems with historical production and consumption data. Default values were applied for the PyPSA-Ein settings. The resulting graph has 2,048 vertices, 2,729 edges, and 14-dimensional feature vectors capturing resistance, reactance, length, and number of parallel lines, nominal power, edge degree etc. Please see the Appendix for more details.
4.2 EXPERIMENTAL. SETTINGS
Evaluation metrics: We apply Pearson's correlation (CORR), Mean Absolute Percentage Error (MAPE), Mean Absolute Error (MAE), and Root Mean Squared Error (RMSE) to compare ground- truth and predicted flows. These metrics are formally defined in the Appendix.
Baselines: Divergence minimization (Div) (Jia et al., 2019) maximizes flow conservation using single regularization parameter X, which we optimize using line search a validation set flows. Multi-Layer Perceptron (MLP) is 2-layer neural network with ReLU activations for all layers that learns to predict flows based on edge features. Graph Convolutional Network (GCN) is a 2- layer graph neural network, also with ReLU activations and Chebyshev convolutions of degree 2, that learns to predict the flows using both edge features and the topology but disregarding flow conservation (Kipf & Welling 2016 Defferrard et al. 2016). We also consider two hybrid baselines. MLP-Div applies the predictions from MLP as priors to Div. Similarly, predictions from GCN are used priors for GCN-Div. For both hybrid models, also optimize the parameter A.
We consider three variations of Algorithm I However, one important modifica- tion is that perform the reverse iterations for each fold-i.e. folds are treated batches in SGD. Bil-MLP and Bil-GCN apply our roverse-mode differentiation approach using an MLP and a GCN as a regularizer. Moreover, both approaches use zero as the prior x("). Bil-GCN-Prior applies the GCN predictions flow priors. Architectures of the neural nets are the same as the baselines.
Our approaches:
4.3 FLOW ESTIMATION ACCURACY
Table compares our methods and the baselines in terms of several metrics using the Traffic and Power datasets. Values of CORR achieved by MLP and GCN for Traffic are missing because they were undefined-they have generated predictions with zero variance for at least one of the train-test folds. All methods suffer from high MAPE eπrors for Power, which is due to an ever-estimation of small flows. Bil-GCN achieves the best results both datasets in terms of all metrics, with 6% and 18% lower RMSF than the best baseline for Traffic and Power, respectively. However, notice that Bil-MLP and Bil-GCN achieve very similar performance for Power and Bil-GCN-Prior does not outperform our other methods. We also show scatter plots with the true vs. predicted flows for some of the best approaches in Figure Traffic has shown to be the more challenging dataset, which can be explained, in part, by training data sparsity-only 38% of edges are labeled.
Predicted fow
1.0
Predicted flow
Predicted flow
1.0
0.8
0.6
6.6
0.6
Predicted
0.4
022
8.4
9.2
0.
0.0
0.4
0.a
0.4
0.2
0.01
0.0
6.
1/
0.4 an
50
0.2 0.4
0.8
08
1.0
88
0'4
in
True flow
True flow
True flow
True flow
(a) GCN. Traffic
(b) Bil-GCN, Traffic
(c) Div, Power
(d) Bil-GCN, Power
Figure 2: Scatter plots with true (x) and predicted (y) flows for two approaches on each dataset. The results are consistent with Table and show that methods are more accurate than the baselines.
7

---

Published as a conference paper at ICLR 2021
Traffic
Power
Method
RMSE
MAE
MAPE
CORR
RMSE
MAE
MAPE
CORR
Div
0.071
0.041
1.23
0.76
0.034
0.015
1419.2
0.93
MLP
0.083
0.055
1.13
0.069
0.043
8334.5
0.61
GCN
0.066
0.040
0.94
0.064
0.043
5622.3
0.64
MLP-Div
0.066
0.041
1.51
0.81
0.033
0.015
1593.5
0.93
GCN-Div
0.071
0.048
1.69
0.81
0.033
0.015
1795.2
0.93
B1-MLL
0.069
0.038
1.05
0.79
0.027
0.011
758.0
0.95
Bil-GCN
0.062
0.034
0.86
0.82
0.027
0.011
788.5
0.95
Bil-GCN-Prior
0.062
0.035
0.91
0.82
0.027
0.011
691.5
0.95
Table 1: Average flow estimation accuracy for the baselines (Div, MLP and GCN) and our methods (Bil-MLP, Bil-GCN and Bil-GCN-Prion using the Traffic and Power datasets. RMSE, MAE and MAPE are errors (the lower the better) and CORR is a correlation (the higher the better). Values of correlation for MLP and GCN using Traffic were undefined. Bil-GCN (ours) outperforms the best baseline for all the metries, with up to 20% lower RMSE than Div using Power.
4.4 ANALYSIS OF REGULARIZERS
Figure iillustrates the regularization function learned by Bil-MLP. We focus on Bil-MLP because can analyzed independently of the topology. Figures 3a 3c
show seatter plots where the and y axes represent the value of the regularizer and features, respectively. For Power, Bil-MLP captures the effect of resistance over flows (Fig. Bay. However, only high values of resistance are mostly dffected-ther is the reason few points can be seen and also explains the good results for Div. We did not find a significant correlation for other features, with the exception of reactance, which is related to resistance. For Traffic, the model learns how the number of lanes constrains the flow at a road segment (Fig. (b). Results for speed limit are more surprising. 45mph roads are less regularized (Fig. 3cb. This is evidence that regularization is affecting mostly traffic bottlenecks in highways- with few lanes but a 65mph speed limit. To further investigate this result, we also show the regularizers over the Traffic topology in Figure High regularization overlaps with well- known congested areas in Los Angeles, CA (c.g.. Highway 5. Southeast). These results are strong evidence that our methods are able to learn the physics of flows in road traffic and power networks.
Resistance x 109)
speed limit (mph)
OF lanes
1.2
1.00
30
points here
0.1
1.0
3.0
0.5
1.5
2.0
0.25
Regularizer
Regularizer
Regularizer
SE DA
0.00
(a) Resistance, Power
(b) Lanes, Traffic
(c) Speed limit, Traffic
(d) Visualization, Traffic
Figure 3: Edge regularizer learned by Bil-ML.P vs. features values (a-c) and visualization of regular-
izers on the Traffic topology (d). Our model is able to learn the effect of the resistance for Power. In Traffic, a higher number of lanes correlated less regularization and lower speed roads (45mph) are less regularized. The regularization is also correlated with congested areas in Los Angeles, CA.
RELATED WORK
Flow graphs are quite ubiquitous in engineering, biomedical and social sciences. Two important properties flow graphs are that their state space defined by graph topology and their dynamics governed by the physics (or logic) of the problem of interest. We refer to Bressan et al. (2014) for a unified characterization the mathematical treatment flow graphs. Notice that these studies do not address the flow inference problem and their applications real data is limited (Herrera al.
8

---

Published as a conference paper at ICLR 2021
2010 Work et al., 2010). Moreover, focus on long term flows (e.g. daily vehicle traffic flows) and not on the dynamics. This simplifies the equations of our model to the conservation law.
Flow inference via divergence minimization was originally proposed in Jia al. (2019). However, their work has not considered edge features and instead applied a single regularization parameter to the norm of the flow vector f in Equation 2 Our work leverages relevant edge features to learn the interplay between flow conservation and local predictions (priors). Thus, we generalize the formulation from Jia al. (2019) the case of learnable regularization function 2(O, X). Our experiments show that the proposed approach achieves superior results in two datasets.
Flow optimization problems, such min-cost flow, max-flow and multi-commodity flow, have long history in computer science (Ahuja et al., 1988 Ford Jr & Fulkerson 2015). These problems impose flow conservation and noiseless flow observations. Our approach relaxes these requirements by minimizing the flow divergence (see Equation 2 Moreover, our problem does not assume edge capacities and costs.
hard constraint, requiring full knowledge of source and sink vertices
The relationship between flow estimation and inverse problems is of particular interest due to the role played by regularization (Engl et al. 1996) in the solution of ill-posed problems. Recent work on inverse problems has also focused on learning to regularize based on data and even learning the forward operator as well-see/aan Are-ddd et al. (2019) for a review. The use of the expression "learning the physics" is also popular in the context of the universal differential equation framework, which enables the incorporation of domain- knowledg from scientific models to machine learning (Raissi
al. 2019 Long et al.. 2018 Rackauckas et al. 2020).
Bilevel optimization in machine learning has been popularized due its applications in hyperparam- eter optimization (Bengio 2000; Larsen et al.) 1996). In the last decade, deep learning has moti- vated novel approaches able to optimize millions of hyperparameters using gradient- -based schemes (Maclaurin et al. 2015 Lorraine al., 2020 PPddregosa 2016). Our flow estimation algorithm is based on reverse-mode differentiation, which is a scalable approach for bilevel optimization (Franceschi al. 2017 Domke 2012 Maclaurin et al., 2015). Another application of bilevel opti-
mization quite related to ours is meta-learning (Franceschi et al. 2018 Grefenstette et al. 2019)
Our problem is also related 2006 Zhou et al. (004)) which is the inference of vertex labels given partial observations. These approaches can be applied for flow estimation via the line graph transformation (Jia et al. (019). The duality between a recent approach for predicting vertex labels Hallac et al. (2015) and min-cost flows was shown in Jung 2020). However, the same relation does not hold for flow estimation.
sumerispereised learning on graphs (Zhu al.
2003
Belkin et al.,
Graph neural network models, which generalize deep learning to graph data, have been shown to outperform traditional semi-supervised learning methods in many tasks (Kipf & Welling 2016] Hamilton et al. 2017 Veličković et al.] 2018). These models have also been applied for traffic forecasting (Li et al., 2017; Yu et al. 20188 Yao et al. 2019). Different from our approach, tradi- tional GNNs do not conserve flows. We show that models outperform GNNs at flow prediction. Moreover, we also apply GNNs as a regularization function in our model.
6 CONCLUSIONS
We have introduced an approach for flow estimation on graphs by combining a conservation law and edge features. Our model learns the physics of flows from data by combining bilevel optimization and deep learning. Experiments using traffic and power networks have shown that the proposed model outperforms set of baselines and learns interpretable physical properties of flow graphs.
While we have focused on learning a diagonal regularization matrix, we want to apply our frame- work to the case of a full matri. We also interested in combining different edge measurements in order to Iearn more complex physical laws, such as described by the fundamental diagram in the LWR model model Lighthill & Whitham (1955); Daganzo [1994 1995): Garavello & Piccoli (2006).
ACKNOWLEDGEMENTS
Research partially funded by the grants NSF IIS #1817046 and DTRA #HDTRAI 19-1-0017

---

Published as a conference paper at ICLR 2021
REFERENCES
Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. Network flows. 1988.
Simon Arridge, Peter Maass, Ozan Öktem, and Carola-Bibiane Schönlieb. Solving inverse problems using data-driven models. Acta Numerica, 28:1-174, 2019.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7(Nov):2399-2434, 2006.
Yoshua Bengio. Gradient- optimization of hyperparameters. Neural computation, 12(8):1889- 1900, 2000.
Léon Bottou and Olivier Bousquet. The tradcoffs large scale learning. In Advances in neural information processing systems, pp. 161-168, 2008
Alberto Bressan, Sunčica Čanié, Mauro Garavello, Michael Herty, and Benedetto Piccoli. Flows on networks: recent results and perspectives. EMS Surveys in Mathematical Sciences, 1(1):47-111, 2014.
Tom Brown, Jonas Hörsch, and David Schlachtberger, Pypsa: Python for power system analysis. arXiv preprint arXiv: 177.v:170..09913, 2017.
Giuseppe Maria Coclite, Mauro Garavello, and Benedetto Piccoli. Traffic flow on a road network. SIAM Journal on Mathematical Analysis, 36(6):1862-1886 2005.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-556 2007.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 244):303-314 1989.
Carlos F Daganzo. The cell transmission model: A dynamic representation of highway traffic sistent with the hydrodynamic theory. Transportation Research Part B: Methodological, 28(4): 269-287, 1994.
Carlos F Daganzo.
The cell transmission model, part ii: network traffic. Transportation Research Part B: Methodological, 29(2):79-92 1995.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Justin Domke. Generic methods for optimization-based modeling. In Artificial Intelligence and Statistics, pp.
2012.
Florian Dörfler, John W Simpson-Poree Porco, and Francesco Bullo. Electrical networks and algebraic graph theory: Models, properties, and applications. Proceedings of the IEFE, 106(5):977-1005, 2018.
Heinz Werner Engl. Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
Lester Randolph Ford Jr and Delbert Ray Fulkerson. Flows in nelworks. Princeton university press, 2015.
Franceschi, M Donini, P Frasconi, and M Pontil. Forward and reverse gradient-based hyperpa- rameter optimization. In ICML, volume 70, pp. 1165-1173. JMLR, 2017.
L Franceschi, P Frasconi, S Salzo, R Grazzi, and M Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In ICML, volume 80, pp. 1563-1572. PMLR (Proceedings of Machine Learning Research), 2018.
10

---

Published as a conference paper at ICLR 2021
M. Garavello and B. Piccoli. Traffic Flow on Networks: Conservation Laws Model. AIMS series applied mathematics, American Institute of Mathematical Sciences, 2006.
Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Htut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, and Soumith Chintala. Generalized inner loop meta- 2019.
learning. arXiv preprint arXiv:
David Hallac, Jure Leskovec, and Stephen Boyd. Network lasso: Clustering and optimization in large graphs. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 387-396, 2015.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2): 2011.
Jozef Hanc, Slavomir Tuleja, and Martina Hancova. Symmetries and conservation laws: Conse- quences of noether's ' theorem. American Journal of Physics, 72(4):428-44) 435, 2004.
Juan C Herrera, Daniel B Work, Ryan Herring, Xuegang Jeff Ban, Quinn Jacobson, and Alexan- dre M Bayen. Evaluation of traffic data obtained via GPS-enabled mobile phones: The mobile century field experiment. Transportation Research Part C: Emerging Technologies, 18(4):568- 583, 2010.
Jonas Hörsch, Fabian Hofmann, David Schlachtberger, and Tom Brown. Pypsa-eur: An open op- timisation model of the european transmission system. Energy Strategy Reviews, 22:207-215, 2018.
Junteng Jia, Michael T. Schaub, Santiago Segarra, and Austin R. Benson. Graph-based semi- supervised and active learning for edge flows. Proceedings of the 25th ACM SIGKDD In- ternational Conference on Knowledge Discovery and Data Mining, pp. 761-771, 2019.
Alexander Jung. On the duality between network flows and network lasso. IEEE Signal Processing Letters, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 141.69141,.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: 1609.02077 2016.
Jan Larsen, Lars Kai Hansen, Claus Svarer, and M Ohlsson. Design and regularization of neural networks: the optimal use of validation set. In Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, pp. 62-71. IEEE, 1996.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusson convolutional recurrent neural net- work: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926, 2017.
Michael James Lighthill and Gerald Beresford Whitham. On kinematic waves ii. a theory of traffic flow long crowded roads. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 229(1178)3317-344 1955.
Zichao Long, Yiping Lu, Xianzhong Ma, and Bin Dong. Pde-net: Learning pdes from data. In 35th International Conference Machine Learning, ICML 2018, pp. 5067-5078. International Machine Learning Society (IMLS), 2018
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. International Conference on Artificial Intelligence and Statistics, pp- 1540-1552. PMLR. 2020.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-bard based hyperparameter optimiza- tion through reversible learning. In International Conference on Machine Learning, pp. 2113- 2122, 2015.
11

---

Published as a conference paper at ICLR 2021
Fabian Pedregosa. 33rd International Conference on International Conference on Machine Learning Volume 48, pp- 737-746, 2016.
Hyperparameter optimization with approximate gradient. In Proceedings of the
Christopher Rackauckas, Yingbo Ma, Julius Martensen, Collin Warner, Kirill Zubov, Rohit Supekar, Dominic Skinner, and Ali Ramadhan. Universal differential equations for scientific machine learning, arXiv preprint 0tt1::2000.043888 2020.
Maziar Raissi, Paris Perdikaris, and George Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378:686-707, 2019.
Paul Richards. Shock waves on the highway. Operations research, 4(1):42-51, 1956.
Albert Tarantola. Inverse problem theory and methods for model parameter estimation, volume 89.
SIAM, 2005.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint urXiv:1909.000 2019.
Daniel B Work, Sébastien Blandin, Olli-Pekka Tossavainen, Benedetto Piccoli, and Alexandre M Bayen. traffic model for velocity data assimilation. Applied Mathematics Research eXpress, 2010(1):1-35, 2010.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2018.
Huaxiu Yao, Xianfeng Tang, Hua Wei, Guanjie Zheng, and Zhenhui Li. Revisiting spatial-temporal similarity: A deep learning framework for traffic prediction. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 33, pp. 5668-5675, 2019.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Confer- ence on Artificial Intelligence, pp.
2018.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal. Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. Advances in Neural Information Processing Systems, pp. 321-328, 2004.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on Machine learning (ICML-03), pp. 912-919, 2003.
12

---

Published as a conference paper at ICLR 2021
Symbol V 3 m E' 3 m' X E Rmxd [(e E Rd fe Rm fe E R fe Rm fe E IR
Meaning
Flow graph Set of vertices in g Size of V
Set of edges in G
Size of &
Set of observed edges
Size of E
Edge feature matrix
Features of edge
Complete flow vector
Flow for edge
Observed flow vector Observed flow for edge Incidence matrix of G Regularization function
B
( X ((0) +) E R+
(()) E I
Flow prior
Regularization parameters
Ω
Domain of F
X E mm-
Estimated vector of missing flows
X E Rm-m'
True vector of missing flows
x Rm-m'
Prior for missing flows
H Rmxm
Map from f to
f E R
Vector with observed flows or 0 otherwise Regularization function (diagonal matrix) Number of folds in validation
0) E R(m (mmm²)
K
Number of outer iterations for Algorithm Number of inner iterations for Algorithm
J
Outer learning rate for Algorithm
3
Inner learning rate for Algorithm
(xx, θ)
Outer objective Inner objective
(e(x)
D X 1. θ;-1) 6
One step of SGD
Estimate of Ve V (x, θ;-1)
H
Matrix H for fold &
Qs fx
Matrix Q for fold i:
Vector f for fold k
Table 2: Table of the main symbols used in this paper.
A TABLE OF SYMBOLS
Table 2 lists the main symbols used in our paper.
B BILEVEL OPTIMIZATION WITH GRAPH NEURAL NETWORKS
This section is an extension of Section 3.3 Here, we consider the case where 2(X;)) is a GNN:
(X θ) diog(GNN(XX.,.) O,
(8)
For instance, we apply a 2-layer spectral Graph Convolutional Network (GCN) with Chebyshev
convolutions (Defferrard et al. 2016 Kipf & Welling
2016 Hammond al. 2011)
Z'
Z Σ
((x:0) = diag
ReLU
Σ
To (L)ReLU
Ts (L)
4-(2)
(9)
13

---

Published as a conference paper at ICLR 2021
where L = 2/ Amax I, L is the normalized Laplacian of the undirected version of the line graph G' of G. Amaz is the largest eigenvalue of L, T'2(L) is a Chebyshev polynomial of L with order and W!") is the matrix of learnable weights for the z-th order polynomial at the layer i. In a line graph, each vertex represents an edge of the undirected version of & and two vertices are connected if their corresponding edges in G are adjacent. Morever L are the adjacency and degree matrices of g Chebyshev polynomials are defined recursively, with (v) 2yT2-1(00 (y) and (v()) = y/-
D-112 AD-1//2 where A and D
In our experiments, we compare GCN against MLP regularization functions. We have also applied the more popular non-spectral graph convolutional operator (Kipf & Welling) (016) but preliminary results have shown that the Chebyshev operator achieves better performance in flow estimation.
C EXTENDED EXPERIMENTAL SECTION
This section in an extension Section 4
C.I MORE DETAILS ON DATASETS
Flow data was collected from the Caltrans-the California Department of Transportation PeMS (Performance Measurement System) Sensors are placed at major highways in the state. We use sensor geo-locations and other attributes to approximately match them to compressed version of road network extracted from Openstreetmapf" The compression merges any sequence of segments without a branch, these extra edges would not affect the flow estimation results. We emphasize that this dataset is not of as high quality as Power, due to possible sensor malfunction and matchings of sensors to the wrong road segments. This explains why flow estimation is more challenging in Traffic. Figure 4 is a visualization of our traffic dataset with geographic (lat-long) located vertices and colors indicating light versus heavy traffic (compared the average). The road segments in the graph (approximately) cover the LA County area. We show the map (from Openstrectmap) of the area covered by our road network in Figure
Traffic:
Power: We will provide more details on how we build the power dataset. PyPSA (Python for Power System Analsys) is toolbox for the simulation of power systems (Brown et al. 2017). We applied the European transmission system (PyPSA-Eur), which covers the ENTSO-E area (Hörsch et al., 2018). to generate single network snapshot. Besides the PyPSA-Eur original set of edges, which we will refer to as line edges, we have added a set of bus edges. These extra edges allow us to represent power generation and consumption as edge flows. For the line edges, we cover the follow- ing PyPSA attributes (with their respective PyPSA identifier reactance (x), resistance(r), capacity (s nom), whether the capacity s nom can extended (s nom extendable), the capital cost of extend- ing s_nom (capital_cost) the length of the line (length), the number of parallel lines (num (ummparallee) and the optimized capacity (s_nom_opt) For bus lines, the only attribute is the control strategy (PQ, PV, Slack), Notice that we create single vector representation for both line and bus lines by adding an extra indicator position (line or bus). Moreover, categorical attributes (e.g., the control strategy) were represented using one-hot encoding. Figure 6 is visualization of power dataset with geographic (lat-long) located vertices and colors indicating high versus low power (compared to the average).
C.2 EVALUATION METRICS
We apply the following evaluation metries for flow estimation. Let firee and fpred be m'- dimensional vectors with true and predicted values for missing flows associated to edges in E E".
Correlation (Corr):
cov(fpred: firue)/ ) (fore(()))))))) o (ftrue))
where cov is the covariance and a is the standard deviation.
'Source:
2 SSouree: hts
14

---

Published as a conference paper at ICLR 2021
Figure 4: Visualization of our traffic network with geo-located vertices. Edges in grey have missing flows, edges red have traffic above the average and edges in blue have traffic below the average. Better seen in color. See Figure for map of the area.
Lancaster
Quartz Hill
Palmdale
Santa Clantá
Angéles
Naniohal
Forest
simi Valle
Atadena
Glendale
Solendara
West Hollywood
MoMnte Counn
Weme
Los Angeles
Damord
Monica
Montebellc
Tlke Rivra
Inglewood
Downey
Manhuacan
Beach
Compoon
Torrance
Anaheim
Beach
Santa Ana
Hundington
foine
Beach
Figure 5: Road map covered by the road network shown in Figure 4 (from Openstreetmap)
Mean Absolute Percentage Error (MAPE): m m
(Coruele (Sprea)e
Σ
(feruele
3
15

---

Published as a conference paper at ICLR 2021
Figure 6: Visualization of our power network with geo-located vertices. Edges in red have traffic above the average and edges in blue have traffic below the average. Better seen in color.
Mean Absolute Error (MAE):
[fttraele (fpred)el
m'
3E
Root Mean Squared Error (RMSE);
Σ [(forue)e - (Epred)el
m' 6E3RE
Divergence (Div):
Σ fun,o) - Σ (
C.3 MORE EXPERIMENTAL SETTINGS
Train/test splits: We report results of 10-fold cross-validation based on the set of labeled flows. Moreover, we use 10% of training flows for validation.
Implementation") c We have implemented Algorithm I using PoTcrc,, CUDA, and Higher (Grefen- stette al. 2019), a meta-learnigg framework that greatly facilitates the implementation of bilevel optimization algorithms by implicitly performing the reverse iterations for a list of optimization al- gorithms, including SGD. Moreover, our GCN implementation based on the Deep Graph Library (DGL) Wang et al., 2019).
Hardware: We ran our experiments on single machine with 4 NVIDIA GeForce RTX 2080 GPUs (each with 8Gb of RAM) and 32 Intel Xeon CPUs (2.10GHz and 128Gb of RAM).
16

---

Published as a conference paper at ICLR 2021
Hyperparameter settings: We have selected the parameters based RMSE for each method using grid search with learning rate over [10", 10 , 2,102,1000 1010 and number of nodes in the hidden layer 3000 for Min-Div and 5000 for MLP
over [4, 8, 16). The total number of iterations and GCN, all with early stop on convergence after 10 iterations. For our methods (both based on Algorithm 1. set 7 = 10, J 300, 10-2, 10-2 and K 10 in all experiments.
C.4 DIVERGENCE RESULTS
Although the main goal of flow estimation is to minimize the flow prediction loss, we also evaluate how our methods and the baselines perform in terms of divergence (or flow conservation) in Table As expected, MLP and GCN do not conserve the flows. However, interestingly, our methods (BiT- MLP and Bil-GCN) achieve higher flow conservation than Min-Div. This is due to the regularization parameter A, which is tuned based on a set of validation flows.
Traffic
Power
Min-Div
2.94
2.45
MLP
5.69
2.77
GCN
5.71
2.80
Bil-MLP
2.81
2.43
Bil-GCN
2.83
2.43
Bil-GCN-Prior
2.43
2.43
Table 3: Divergence results.
D TRUE VS. PREDICTED FLOWS
Figure
shows seatter plots with the true vs. predicted flows that are missing from Figure
Predicted how
1.01
Predicted flow
Predicted flo
1.0
1.0
0.6
0.8 0.6 9.4
6.6
0.6
b. 94
Predicted
0.6
0.4
0.4
0.2
0.2
0.0
flow
True flow
True flow
flow
(a) MLP, Traffic
(b) Min-Div, Traflic
(c) Bil-MLP, Traffic
(d) Bil-GCN-Prinn Traffic
Prodicted flw
Predicted flov
0.8
Predicted
0.6
Predicted
6.4
8.4
0.4
0.2
0.2
0.2
0.0
0.01
6.0
06
1.0
02
0.4
08
1.5
0.0
0.2
0.6
08
0.
0.4
AG
160
True flow
True flow
True flow
True flow
(e) MLP. Power
(I) GCN, Power
(g) Bil-MLP. Power
(h) Bil-GCN-Prior, Power
Figure 7: Scatter plots with true (x) and predicted (y) flows for remaining methods (beyond the ones shown in Figure
D.I VISUALIZATION REGULARIZER POWER
Figure shows the regularizers over the Power network topology. As discussed in Section 4.4 the regularizer affects mostly a few top resistance edges. For the remaining ones, regularizers have small value. Notice that these high resistance edges associated with lines transmitting small amounts power, as shown in Figure Figure 6 and have a large impact on the overall flow estima- tion accuracy.
17

---

Published as a conference paper at ICLR 2021
0.40
0.35
0.30
0.25
0..0
0.15
0.10
0.05
0.00
Figure 8: Visualization regularizers on the Power network topology. We highlight edges with
large vaues of regularizer. Better seen in color.
Traffic
Power
Method
Training
Test
Training
Test
Min-Div
424.4
0.09
364.2
0.01
MLP
21.95
0.10
12.32
0,01
GCN
2.43
0.09
0.77
0.01
Bil-MLP
1860.2
0.08
369.7
0.01
Bil-GCN
1870.1
0.09
346.7
0.01
Bil-MLP-Prid
1886.
0.01
334.1
0.01
Table 4: Average training and test times (in seconds) for our methods and the baselines (in seconds).
D.2 RUNNING TIME
Table 4 shows the average rumning times-over over the 10-fold gross-validation- of our methods and the baselines for the Traffic and Power datasets. We show both training and test times. The results show that our reverse-mode differentiation algorithm adds significant overhead on training time for Traffic, taking up to 4 times longer than Min-Div finish. As described in Section (344 this is due mainly to the cost of computing and storing the inner problem iterations. On the other hand, all the methods are efficient at testing. GCN converged quickly (due to early stopping) for both datasets. However, it achieved poor results for Power, as shown in Table which is sign of overfitting or underfitting. Notice that the results reported are the best in terms of RMSE.
18


Reviews:
[{"review_id": "hn81JFGxyRm", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the very important problem of incorporating physics into machine learning model with special focus on the missing flow estimation problem. It proposes the a flow-estimation model that combines the reverse-model differentiation and neural network considering the edge features. Empirical results on two real-world datasets show very promising results with interpretable physical properties.\n\nClean presentation and easy to follow.\n\nStrength:\n- The investigated problem of incorporating physics into machine learning model is very important.\n- The idea is combining reverse-mode differentiation into the modeling is intuitive and also shown to be effective.\n- The proposed algorithm achieves improved results and also show intuitive interpretation.  \n- The paper provides detailed information implementation about experiments, which make the result more convincing and easier to reproduce. \n\nHere are some minor concerns:\n- The proposed algorithm applies to problems on the flow graphs. Yet, for many applications on flow graphs, e.g., traffic speed (instead of flow) prediction, it may not be straight-forward to apply the proposed algorithm.\n- It is will be interesting to see if the flow preservation can be incorporated directly in the model forward path of training instead of using a regularizer.", "extra_scores": {}, "extra_text": {}}, {"review_id": "e5DTLsvMpV_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors introduce a method for missing flow estimation. These method has potential to address some important applications in transportation, power systems and water management. One major difference compared with the previous work is that edge features are incorporated into the optimization process so that the model has a better chance at learning edge-specific patterns. The experimental results have shown some success of the proposed method in traffic and power datasets.\n\nThere are several major issues with the paper:\n1. The model is based on the assumption of flow conservation. However, this is not always true in real-world scenarios. The power can be generated or consumed while water flow can also be affected by precipitation. \n\n2. The novelty is limited as most parts are based on existing work. The authors claim that this method combines physics and ML but I did not see physics being used anywhere in designing the model (except for the conservation). The use of matrix Q (and edge features) may not necessarily learn patterns that are consistent to underlying physics (since it is still learned automatically).\n\n3. Notation used in the paper is confusing, even if people can still get most of it after reading through the entire paper. For example, authors may want to include the definition of x (missing flows) in Section 2. In Eq. 1, do you need the operator \\sum_vi?\n\n4. An alternative way to think about this problem is to train a predictive model that predicts x from edge features (maybe using a graph neural net) and then enforce the flow conservation. What is the difference between this predictive framework and the proposed bilevel optimization framework? It would be great to compare with other predictive method. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "N1ikvhW09l5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a parametric regularizer for estimating unobserved flows in networks, incorporating edge features and other side information. The parameters of the regularizer are learned by means of minimizing the empirical cross-validated MSE. Regularization is necessary because the basic problem, while convex, typically is under-constrained; resulting in a infinite space of solutions which match the observed data.  \n\nThe paper is clearly written and easy to follow. It conceptually follows the universal-differential-equation (UDE) framework for integrating physics and machine learning, in which certain elements of a physical model are replaced by a parametric model which can be trained from data. This connection makes the work topical, and a small step forward in physics-informed machine learning.\n\nFor this particular problem, it seems that (i) the prior is indispensable, some prior (perhaps implicit) will be contained in any regularization, and (ii) the learned parameters may depend implicitly on the prior. This brings up two difficulties. Where does one obtain a (good) prior if one does not have one already? And, how can we hope the parameterized regularizer will generalize for new priors? Perhaps by virtue of it's simplicity?\n\nOther potential issues I should like to have seen addressed are: \n\nThe model is well suited for instantaneous flows. For the traffic problem, it seems it is predicting current flow from current flow. Yet, it takes time for cars to move about. It would be nice to see temporal dynamics included.\n\nOnly diagonal regularizers are considered. Can the authors comment on learning more general regularizing matrices? \n\nCan the proposed learning algorithm (or similar) be used to inform which edges ought to be measured to maximize one's ability to impute the missing flows? If so, how? If not, why?\n\nFinally, and not least, the cross-validation routine appears to equally weight each edge. Yet, some edges may be more constrained than others. Certainly, each fold will have it's own, potentially different, infinite subspace of solutions to the unregularized problem. Failing to account for this may bias the learning algorithm. One may see undue performance degradation when applying a trained model to a different pattern of observed flows for the same network.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "08VfxWmGUtA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "authors study the problem of learning flows form partially observed flow networks. The estimationg of unobserved flows is based on flow conservation and edge features. \n\nonly little theorerical analysis is offered: \n- does the proposed method converge?\n- is the learning problem (bi-level optimization problem) intriniscally hard (non-convex)? \n\nim also missing a discussion of how the proposed method relates to min-cost flow problems which are quite well-studiedl see the textbook Network Optimization: Continuous and Discrete Models  by Bertsekas. \nA recent line of work connects min-cost flow problems with non-smooth convex optimization: \n\nA. Jung, \"On the Duality Between Network Flows and Network Lasso,\" in IEEE Signal Processing Letters, vol. 27, pp. 940-944, 2020, doi: 10.1109/LSP.2020.2998400.\n\nthe numerical experiments are not very convincing. Also, it is unclear how the edge features are obtained precisely for the traffice network example. It is mentioned that we know in-degree, out-degree and number of lanes. How is the in-degree of an edge defined?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper combines bi-level optimization and reverse mode-differentiation for flow estimation on networks. Most reviewers think the idea of incorporating physical constraints is interesting and novel, and the experiments convincing.
Decision: Accept (Poster)