summaries: This paper provides a method for addressing the "prediction + programming" problem in the case where the programming problem contains a $\max(z,0)$ term in the objective. To do so, the authors rewrite the optimization problem as an unconstrained optimization problem by converting all hard constraints of the optimization problem to soft constraints in the objective. They then pick the coefficients of those soft constraints in a way that is meant to prevent constraint violations, and then relax these soft constraints via a surrogate function. They then embed the resultant approximate optimization problem within a method where some $\theta$ is output by a neural network, the approximate optimization problem is solved for that value of $\theta$, and gradients are updated by differentiating end-to-end through the approximate optimization problem. The authors demonstrate their method on three synthetic settings, and report improved performance over two-stage methods and SPO+.

summaries: This paper presents an approach for "predict, then optimize" problems that is amenable to derivative-based learning methods. It involves converting hard constraints into soft constraints (i.e. implicitly enforced through objective penalization). The main theoretical contributions are bounds on the magnitude of objective change that can be attributed to infeasibility with respect to the original hard constraints.

summaries: The paper develops a surrogate function with closed-form solution for objective functions with "soft constraints," here defined as those with the term $\alpha^T \\max\\{0,z(x)\\}$ for affine $z$, component-wise $\\max$, and $\alpha > 0$. The goal is to apply such functions within the context of smart "predict-then-optimize" (SPO) by also relaxing the hard constraints with a sufficiently large penalty $\alpha$. To develop their surrogate, the authors evaluate bounds on the utility gained when violating the soft constraints using primarly a geometric perspective, specifically evaluating the angles or corners of infeasible points with respect to the convex hull of feasible solutions (and related properties). Numerical results compare their approach with the standard SPO+ loss function and a DF metric for portfolio optimization.

summaries: The paper proposes a new method to integrate soft constraints in the predict+programming paradigm that focuses on mathematical programming models with a prediction component that needs to be considered during optimization/solving. The new method works by reformulating the problem into piecewise linear constraints and then optimizing a surrogate for the original problem. A theoretical analysis and motivation is provided as well as an experimental evaluation that underlines the effectiveness of the method.

abstractText: Prediction+optimization is a common real-world paradigm where we have to predict problem parameters before solving the optimization problem. However, the criteria by which the prediction model is trained are often inconsistent with the goal of the downstream optimization problem. Recently, decision-focused prediction approaches, such as SPO+ and direct optimization, have been proposed to fill this gap. However, they cannot directly handle the soft constraints with the max operator required in many real-world objectives. This paper proposes a novel analytically differentiable surrogate objective framework for real-world linear and semi-definite negative quadratic programming problems with soft linear and non-negative hard constraints. This framework gives the theoretical bounds on constraints’ multipliers, and derives the closed-form solution with respect to predictive parameters and thus gradients for any variable in the problem. We evaluate our method in three applications extended with soft constraints: synthetic linear programming, portfolio optimization, and resource provisioning, demonstrating that our method outperforms traditional two-staged methods and other decision-focused approaches.

authors:
Chuan Luo
Bo Qiao
Xin Chen
Pu Zhao
Randolph Yao
Hongyu Zhang
Wei Wu
Andrew Zhou
Qingwei Lin

title: Intelligent virtual machine provisioning in cloud computing

venue: In Proceedings of IJCAI

authors:
Sirikarn Chansombat
Pupong Pongcharoen
Christian Hicks

title: A mixed-integer linear programming model for integrated production and preventive maintenance scheduling in the capital goods industry

venue: International Journal of Production Research, 57:1–22,

authors:
Kai Wang
Bryan Wilder
Andrew Perrault
Milind Tambe

title: Automatically learning compact quality-aware surrogates for optimization problems

venue: NeurIPS

authors:
Emir Demirovi
Peter Stuckey
Tias Guns
James Bailey
Christopher Leckie
Kotagiri Ramamohanarao
Jeffrey Chan

title: Dynamic programming for predict+optimise

venue: Proceedings of the AAAI Conference on Artificial Intelligence, 34:1444–1451,

authors:
Gartheeban Ganeshapillai
John Guttag
Andrew Lo

title: Learning connections in financial time series

venue: Proceedings of the 30th International Conference on Machine Learning,

title: Using a financial training criterion rather than a prediction criterion

venue: Int. J. Neural Syst.,

authors:
Bryan Wilder
Bistra Dilkina
Milind Tambe

title: Melding the data-decisions pipeline: Decisionfocused learning for combinatorial optimization

venue: In The Thirty-Third AAAI Conference on Artificial Intelligence,

authors:
Adam Elmachtoub
Paul Grigas

title: Smart "predict, then optimize

venue: Management Science,

authors:
Priya L. Donti
Brandon Amos
J. Zico Kolter

title: Task-based end-to-end model learning in stochastic optimization

venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,

authors:
Yang Song
Alexander Schwing
Richard
Raquel Urtasun

title: Training deep neural networks via direct loss minimization

venue: In Proceedings of The 33rd International Conference on Machine Learning,

authors:
Brandon Amos
J. Zico Kolter

title: OptNet: Differentiable optimization as a layer in neural networks

venue: Proceedings of the 34th International Conference on Machine Learning,

title: Differentiable Optimization-Based Modeling for Machine Learning

venue: PhD thesis,

authors:
Akshay Agrawal
Brandon Amos
Shane Barratt
Stephen Boyd
Steven Diamond
J. Zico Kolter

title: Differentiable convex optimization layers

venue: In Advances in Neural Information Processing Systems,

title: Portfolio Selection: Efficient Diversification of Investments

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga
Alban Desmaison
Andreas Kopf
Edward Yang
Zachary DeVito
Martin Raison
Alykhan Tejani
Sasank Chilamkurthy
Benoit Steiner
Lu Fang
Junjie Bai
Soumith Chintala

title: Pytorch: An imperative style, highperformance deep learning library

venue: Advances in Neural Information Processing Systems

authors:
A. Griewank
A. Walther

title: Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Second Edition

venue: Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM,

title: Matrix Differential Calculus with Applications in Statistics and Econometrics, Third Edition

venue: Wiley Series in Probability and Statistics

authors:
Stephen Boyd
Lieven Vandenberghe

title: Convex Optimization

authors:
Jonas Peters
Dominik Janzing
Bernhard Schölkopf

title: Elements of causal inference

authors:
Vinod Nair
Geoffrey E. Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Proceedings of the 27th International Conference on International Conference on Machine Learning,

authors:
John Duchi
Elad Hazan
Yoram Singer

title: Adaptive subgradient methods for online learning and stochastic optimization

venue: Journal of Machine Learning Research, 12:2121–2159,

title: Predict daily electric consumption with neural networks, 2020. URL https: //www.brownanalytics.com/load-forecasting

authors:
Aaron Ferber
Bryan Wilder
Bistra Dilkina
Milind Tambe

title: Mipaal: Mixed integer program as a layer

venue: In AAAI Conference on Artificial Intelligence,

authors:
Jayanta Mandi
Tias Guns

title: Interior point solving for lp-based prediction+optimisation

venue: Advances in Neural Information Processing Systems,

authors:
Di Chen
Yada Zhu
Xiaodong Cui
Carla Gomes

title: Task-based learning via task-oriented prediction network with applications in finance

venue: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,

authors:
Arthur Mensch
Mathieu Blondel

title: Differentiable dynamic programming for structured prediction and attention

venue: In 35th International Conference on Machine Learning,

authors:
Josip Djolonga
Andreas Krause

title: Differentiable learning of submodular models

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

venue: In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32,

authors:
Quentin Berthet
Mathieu Blondel
Olivier Teboul
Marco Cuturi
Jean-Philippe Vert
Francis Bach

title: Learning with differentiable perturbed optimizers

venue: arXiv preprint arXiv:2002.08676,

heading: 1 Introduction

text:
Mathematical optimization (a.k.a. mathematical programming), e.g., linear and quadratic programming, has been widely applied in decision-making processes, such as resource scheduling [1], goods production planning [2], portfolio optimization [3], and power scheduling [4]. In practice, problem parameters (e.g., goods demands, and equity returns) are often contextual and predicted by models with observed features (e.g., history time series). With the popularity of machine learning techniques and increasing available data, prediction+optimization has become a normal paradigm [5]. ∗Contributed during internship at Microsoft Research. † Corresponding Author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Prediction becomes critical to the performance of the full prediction+optimization workflow since modern optimization solvers (e.g., Gurobi [6] and CPLEX [7]) can already efficiently find optimal solutions for most large scale optimization problems. Traditionally, prediction is treated separately as a general supervised learning problem and learned through minimizing a generic loss function (e.g., mean squared error for regression). However, studies have shown that minimization of the fitting errors does not necessarily lead to better final decision performance [8, 9, 10, 11].
Recently, a lot of efforts on using optimization objective to guide the learning of prediction models have been made, which are decision-focused when training prediction models instead of using traditional prediction metrics, e.g. mean squared error losses. For linear objectives, the ‘Smart Predict then Optimize’ ([10]) proposes the SPO+ loss function to measure the prediction errors against optimization objectives, while direct optimization ([12]) updates the prediction model’s parameters by perturbation. For quadratic objectives, OptNet [13, 14] implements the optimization as an implicit layer whose gradients can be computed by differentiating the KKT conditions and then back propagates to prediction neural network. CVXPY [15] uses similar technologies with OptNet but extends to more general cases of convex optimization. However, all the above state-of-the-art approaches do not contain the soft constraints in their objectives. In this paper, We consider linear ‘soft-constraints’, a penalty in the form of max(z, 0), where z = Cx− d is a projection of decision variable x ∈ Rn and context variables C ∈ Rm×n, d ∈ Rm. Such soft constraints are often required in practice: for example, they could be the waste of provisioned resources over demands or the extra tax paid when violating regulatory rules. Unfortunately, the max(·, 0) operator is not differentiable and thus cannot be directly handled by these existing approaches. To differentiate soft constraints is a primary motivation of this paper.
In this paper, we derive a surrogate objective framework for a broad set of real-world linear and quadratic programming problems with linear soft constraints and implement decision-focused differentiable predictions, with the assumption of non-negativity of hard constraint parameters. The framework consists of three steps: 1) rewriting all hard constraints into piece-wise linear soft constraints with a bounded penalty multiplier; 2) using a differentiable element-wise surrogate to substitute the piece-wise objective, and solving the original function numerically to decide which segment the optimal point is on; 3) analytically solving the local surrogate and obtaining the gradient; the gradient is identical to that of the piecewise surrogate since the surrogate is convex/concave such that the optimal point is unique.
Our main contributions are summarized as follows. First, we propose a differentiable surrogate objective function that incorporates both soft and hard constraints. As the foundation of our methodology, in Section 3, we prove that, with reasonable assumptions generally satisfied in the real world, for linear and semi-definite negative quadratic programming problems, the constraints can be transformed into soft constraints; then we propose an analytically differentiable surrogate function for the soft constraints max(·, 0). Second, we present the derived analytical and closed-form solutions for three representative optimization problems extended with soft constraints in Section 4 – linear programming with soft constraints, quadratic programming with soft constraints, and asymmetric soft constraint minimization. Unlike KKT-based differentiation methods, our method makes the calculation of gradients straightforward for predicting context parameters in any part of the problem. Finally, we apply with theoretical derivations and evaluate our approach in three scenarios, including synthetic linear programming, portfolio optimization, and resource provisioning in Section 4, empirically demonstrate that our method outperforms two-stage and other predict+optimization approaches.

heading: 2 Preliminaries

heading: 2.1 Real-world Optimization Problems with Soft Constraints

text:
Our target is to solve the broad set of real-world mathematical optimization problems extended with a max(z, 0) term in their objectives where z depends on decision variables and predicted context parameters. In practice, max(z, 0) is very common; for example, it may model overhead of underprovisioning, over-provisioning of goods, and penalty of soft regulation violations in investment portfolios. We call the above max(z, 0) term in an objective as soft constraints, where z ≤ 0 is allowed to violate as long as the objective improves.
The general problem formulation is
max x
g(θ, x)− αT max(z, 0), z = Cx− d, s.t. Ax ≤ b,Bx = c, x ≥ 0 (1)
where g is a utility function, x ∈ Rn the decision variable, and θ ∈ Rn the predicted parameters. Based on observations on a broad set of practical problem settings, we impose two assumptions on the formulation, which serves as the basis of following derivations in this paper. First, we assume A ∈ Rm1×n ≥ 0, b ∈ Rm1 ≥ 0, B ∈ Rm2×n ≥ 0 ,and c ∈ Rm2 ≥ 0 hold. This is because for problems with constraint on weights, quantities or their thresholds, these parameters are naturally non-negative. Second, we assume the linearity of soft constraints, that is z = Cx − d, where z ∈ Rm3 , C ∈ Rm3×n, and d ∈ Rm3 . This form of soft constraints make sense in wide application situations when describing the penalty of goods under-provisioning or over-provisioning, a vanish in marginal profits, or running out of current materials.
Now we look into three representative instances of Eq.1, extracted from real-world applications.
Linear programming with soft constraints, where g(x, θ) = θTx. The problem formulation is
max x
θTx− αT max(Cx− d, 0), s.t. Ax ≤ b,Bx = c, x ≥ 0 (2)
where α ≥ 0. Consider the application of logistics where θ represents goods’ prices, {A, B, C} are the capability of transportation tools, and {b, c} are the thresholds. Obviously, A, b,B, c ≥ 0 hold. Quadratic programming with soft constraints, where g(θ, x) = θTx − xTQx. One example is the classic minimum variance portfolio problem [16] with semi-definite positive covariance matrix Q and expected return θ to be predicted. We extend it with soft constraints which, for example, may represent regulations on portions of equities for some fund types. Formally with α ≥ 0, we have:
max x
θTx− xTQx− αT max(Cx− d, 0), s.t. Bx = c, x ≥ 0. (3)
Optimization of asymmetric soft constraints. This set of optimization problems have the objective to match some expected quantities by penalizing excess and deficiency with probably different weights. Such formulation represents widespread resource provisioning problems, e.g., power[4] and cloud resources[1], where we minimize the cost of under-provisioning and over-provisioning against demands. Formally with α1, α2 > 0, we have:
max x −(αT1 max(Cx− d, 0) + αT2 max(d− Cx, 0)), s.t. Bx = c, x ≥ 0. (4)
In this paper, we consider a challenging task where C is a matrix to be predicted with known constants d. In reality, the Cx− d term may represent the "wasted" part when satisfying the actual need of d.

heading: 2.2 Prediction+Optimization

text:
For compactness we write Eq.1 as maxx∈X f(x, θ), where f is the objective function and X is the feasible domain. The solver for f is to solve x∗ = argmaxx∈X f(x, θ). With parameters θ known, Eq.2–4 can be solved by mature solvers like Gurobi [6] and CPLEX [7].
In prediction+optimization, θ is unknown and needs to be predicted from some observed features ξ ∈ Ξ. The prediction model is trained on a dataset D = {(ξi, θi)}Ni=1. In this paper, we consider the prediction model, namely Φ, as a neural network parameterized with ψ. In traditional supervised learning, Φψ is learned by minimizing a generic loss, e.g., L1 (Mean Absolute Error) or L2 (Mean Squared Error), which measures the expected distance between predictions and real values. However, such loss minimization is often inconsistent with the optimization objective f , especially when the prediction model is biased [11].
Instead, decision-focused learning directly optimizes ψ with respect to the optimization objective f , that is, maxψ E(ξ,θ)∼D[f(x̂∗(Φψ(ξ)), θ)]. The full computational flow is illustrated in Fig.1. In
the gradient-based learning, update of ψ’s gradient is ∂r∂ψ = ∂θ̂ ∂ψ
∂x̂∗
∂θ̂ ∂r ∂x̂∗ , where utility r = f(x̂∗, θ).
The Jacobian ∂θ̂/∂ψ is computed implicitly by auto-differentiation of deep learning frameworks (e.g, PyTorch [17]), and ∂r/∂x̂∗ is analytical. The main challenge is to compute ∂x̂∗/∂θ̂, which depends on differentiating the argmax operation. One recent approach is to rewrite the objective to be convex (by adding a quadratic regularizer if necessary), build and differentiate the optimality conditions (e.g.,
KKT conditions) [18] which map θ̂ to the solution x̂∗, and then apply implicit function theorem to obtain ∂x̂∗/∂θ̂. Alternatively, in this paper we propose a novel approach that rewrites the problem as an unconstrained problem with soft constraints and derives analytical solutions, based on our observations on the real-world problem structures and coefficient properties.

heading: 3 Methodology

text:
Our main idea is to derive a surrogate function for f with a closed-form solution such that the Jacobian ∂x∂θ is analytical, making the computation of gradient straightforward. Unlike other recent work [13, 14, 15, 3], our method does not need to solve KKT optimality condition system. Instead, by adding reasonable costs for infeasibility, we convert the constrained problem into an unconstrained one. With the assumption of concavity, we prove that there exist constant vectors β1, β2, β3, such that Eq.1 can be equivalently transformed into an unconstrained problem:
max x L(x) = max x
g(x, θ)−αT max(Cx−d, 0)−βT1 max(Ax−b, 0)−βT2 |Bx−c|−βT3 max(−x, 0) (5)
The structure of this section is as follows. Section 3.1 proves that the three types of hard constraints can be softened by deriving bounds of β1, β2, β3; for this paper, we will assign each entry of the three vectors the equal value (with a slight abuse of notation, we denote β1 = β2 = β3 = β for the proofs of bounds; we align with the worst bound applicable to the problem formulation.) Section 3.2 proposes a novel surrogate function of max(·, 0), such that the analytical form of ∂x∂θ can be easily derived via techniques of implicit differentiation [18] and matrix differential calculus [19] on equations derived by convexity [20]. Based on such derived ∂x∂θ , we develop our end-to-end learning algorithm of prediction+optimization whose detailed procedure is described in Appendix C.

heading: 3.1 Softening the Hard Constraints

text:
For any hard constraints w = Ax − b ≤ 0, we denote its equivalent soft constraints as H(w) = βT max(w, 0). H(w) should satisfy two conditions: 1) for w ≤ 0 (feasible x), H(w) = 0; 2) for w ≥ 0 (infeasible x), H(w) is larger than the utility gain(i.e., improvement of the objective value) R = f(x, θ) − maxx1:Ax1≤b f(x1, θ) by violating Ax − b ≤ 0. Intuitively, the second condition requires a sufficiently large-valued β > 0 to ensure that the optimization on the unconstrained surrogate objective never violates the original Ax ≤ b; to make this possible, we assume that the l2-norm of the derivative of the objective f before conversion is bounded by constant E. The difficulty of requirement 2) is that the distance of a point to the convex hull l is not bounded by the sum of distances between the point and each hyper-plane in general cases, so the utility gain obtained from violating constraints is unbounded. Fig. 2-(a) shows such an example which features the small angle between hyper-planes of the activated cone. We will refer such kind of ’unbounding’ as "acute angles" below.
The main effort of this subsection is to analyze and bound the effect caused by such acute angles. Given a convex hull C = {z ∈ Rn|Az ≤ b} (A ≥ 0 is not required here) and any point x 6∈ C, let x0 ∈ C be the nearest point of C to x, and A′x ≥ b′ represent all active constraints at x, then all such active constraints must pass through x0.2 The domain K = {z ∈ Rn|A′z ≥ b′} is a cone or degraded
2Otherwise, there must exist an active constraint i and a small neighbourhood of x0, say B(x0, ), such that ∀z ∈ B(x0, ), Aiz − bi 6= 0, which implies that either constraint i is inactive (< 0) or x0 6∈ C (> 0).
cone where the tip of the cone is a subspace of Rn. For the rest of the paper, we will call K activated cone, as shown in Fig. 2. Note that for any degraded activated cone, x− x0 is always perpendicular to the tip subspace; therefore, we may project the cone onto the complementary space of the tip and get the same multiplier bound on the projected activated cone with lower dimensions.
Ideally, we aim to eliminate the utility gain R obtained from violating A′x ≤ b′ with the penalty βT (A′x− b′), i.e., ensure βT (A′x− b′) ≥ R hold for any x. For the compactness of symbols and simplicity, we will assume that the main objective is g(x, θ) = θTx in this section; however note that our proofs apply with the existence of soft constraints and quadratic terms in g, which is discussed at the beginning of Appendix A. With such assumption, we now give a crucial lemma, which is the core of our proof for most of our theorem:
Lemma 1. (Bounding the utility gain) Let R = f(x, θ) − maxx1∈C f(x1, θ) be the utility gain, then R ≤ f(x, θ) − f(x0, θ) ≤ Ecos p0 ∑n i=1(A ′ ix − b′i), where x is an infeasible point, A′x ≤ b′ the active constraints at x, p0 = ∠(A′i ∗ , θ∗) where A′i
∗ and θ∗ are the optimal solution of maxθ minA′i cos∠(A ′ i, θ) (i.e., the maximin angle between θ and any hyperplane of the activated cone K = {z ∈ Rn|z − x0 ∈ cone(A′)}), and x0 the projection of x to the tip of cone C = {z ∈ Rn|A′z ≤ b′}. E is the upper bound of ||θ||2. ∠(·, ·) denotes the angle of two vectors.
Thus, Ecos p01 is a feasible choice of β, and it suffices by finding the lower bound for cos p0. For the rest of the section, we find the lower bound of cos p0 by exploiting the assumed properties of A′, e.g., A′ ≥ 0; we give the explanation of the full proofs for all theoretical results in Appendix A.

heading: 3.1.1 Conversion of Inequality Constraints Ax ≤ b

text: Let us first consider the constraints w = Ax − b ≤ 0, where A ≥ 0, b ≥ 0. It is easy to prove that given A ≥ 0 and b ≥ 0, the distance of a point to the convex hull Ax ≤ b is bounded. More rigorously, we have the following theorem, which guarantees the feasibility of softening the hard constraints of inequalities Ax ≤ b: Theorem 2. Assume the optimization objective θTx with constraints Ax ≤ b, where A ≥ 0, and b ≥ 0. Then, the utility gain R obtained from violating Ax − b ≤ 0 has an upper bound of O( ∑ i max(wi, 0)E), where w = A ′x− b′, and A′x ≤ b′ is the active constraints.

heading: 3.1.2 Conversion of Inequality Constraints x ≥ 0

text:
With inequality constraints Ax ≤ b converted, we now further enforce x ≥ 0 into soft constraints. It seems that the constraint of this type may form a very small angle to those in w = Ax− b. However, as −x is aligned with the axes, we can augment x ≥ 0 into soft constraints by proving the following theorem:
Theorem 3. When there is at least one entry of x ≥ 0 in the activated cone, the utility gain R from deviating the feasible region is bounded by O(n 1.5E ∑ imax(wi,0)
sin p ), where p is the smallest angle between axes and other constraint hyper-planes and w is the union of Ax− b and −x.
Hence, we can set β = O(n 1.5E sin p ). Specially, for binary constraints we may set β = O(n 1.5E):
Corollary 4. For binary constraints where the entries of A are either 0 or 1, the utility gain R of violating x ≥ 0 constraint is bounded by O(n1.5E ∑ i max(wi, 0)), where wi = Aix− bi or −x.
which gives a better bound for a set of unweighted item selection problem (e.g. select at most k items from a particular subset).

heading: 3.1.3 Conversion of Equality Constraints Bx = c

text:
Finally, we convert Bx = c into soft constraints. This is particularly difficult, as Bx = c implies both Bx ≤ c and −Bx ≤ −c, which will almost always cause acute angles. Let’s first consider a special case where there is only one equality constraints and A is an element matrix In×n. Theorem 5. If there is only one equality constraint Bx = c (i.e., B degrades as a row vector, such like ∑ i xi = 1) and special inequality constraints x ≥ 0, Ix ≤ b, then the utility gain R from violating constraints is bounded by O(n 1.5E ∑ i max(wi,0)
sin p ), where p is the same with theorem 3, w is the union of Bx− c and −x.
Intuitively, when there is only one equality constraint, the equality constraint can be viewed as an unequal one, for at most one side of the constraint can be in a non-degraded activated cone. Thus, we can directly apply the proof of Theorem 2 and 3, deriving the same bound O(n
1.5E sin p ) for β.
Finally, we give bounds for general Ax ≤ b, Bx = c with A, b,B, c ≥ 0 as below: Theorem 6. Given constraints Ax ≤ b, x ≥ 0, and Bx = c, where A,B, b, c ≥ 0, the utility gain R obtained from violating constraints is bounded by O( √ nλmax ∑ i max(wi, 0)), where λmax is the upper bound for eigenvalues of PTP (P : x→ Px is an orthogonal transformation for an n-sized subset of normalized row vectors in A,B and −I), and w is the union of all active constraints from Ax ≤ b, x ≥ 0, Bx ≤ c and −Bx ≤ −c.
In this theorem, P is generated by taking an arbitrary n-sized subset from the union of row vectors in A,B and −I , orthogonizing the subset, and using the orthogonal transformation matrix as P ; there are ( n+m1+m2
n
) different cases of P , and λmax is the upper bound of eigenvalues of PTP
over all possible cases of P . Note that there are no direct bounds on λmax with respect to n and the angles between hyper-planes. However, empirical results (see Appendix A for details) show that for a diverse set of synthetic data distributions, λmax = O(n2) follows. Therefore, empirically we can use a bound O(n
2.5E sin p ) for β. 3 So far, we have proven that all hard constraints can be transformed into soft constraints with bounded multipliers. For compactness, Eq.5 is rewritten in a unified form:
L(x) = g(x, θ)− γT ·max(C′x− d′), where γ = [
α
O(n 2.5E sin p )1
] , C′ =  C A −B B −I , d′ =  d b −c c 0  (6)

heading: 3.2 The Unconstrained Soft Constraints

text:
As Eq.5 is non-differentiable for the max operator, we need to seek a relaxing surrogate for differentiation. The most apparent choice of the derivative of such surrogate S(z) for z = C ′x − d′ is sigmoidal functions; however, it is difficult to derive a closed-form solution for such functions, since sigmoidal functions yield z in the denominator, and z cannot be directly solved because C is not invertible (referring to Appendix B for detailed reasons). Therefore, we have to consider a piecewise roundabout where we can first numerically solve the optimal point to determine which segment the optimal point is on, and then expand the segment to the whole space. To make this feasible, two assumptions must be made: 1) this function must be differentiable, and 2) the optimal point must be unique; to ensure this, the surrogate should be a convex/concave piece-wise function. The second property is for maintaining the optimal point upon segment expansion. Fortunately, there is one simple surrogate function satisfying our requirement:
S(z) =  0 if z < − 1 4K K(z + 1 4K )2 if − 1 4K ≤ z ≤ 1 4K
z if z ≥ 1 4K
(7)
3For real optimization problems, we can sample A′ from A and estimate the largest eigenvalue of PTP .
Let M and U be diagonal matrices as the indicator of S(z), which are Mi,i = 2K[− 14K ≤ zi ≤ 1 4K ] and Ui,i = [ 14K < zi], where [·] is an indicator function. K > 0 is a hyper-parameter that needs to be balanced. Larger K makes the function closer to original; however, if K is too large, then the training process would be destabilized, because when the prediction error is large at the start of the training process, ∂f
∂θ̂ |x̂ might be too steep. Then consider the optimal point for the unconstrained optimization
problem maximizing θTx− γT max(C ′x− d′, 0), by differentiaing on both sides, we can obtain:
θ = C′TMdiag(γ)(C′x− d′) + C′T ( 1 4K M + U)γ (8)
This equation reveals the closed-form solution of x with respect to θ, and thus the calculation of ∂x∂θ becomes straightforward:
∂x ∂θ = (C ′TMdiag(γ)C ′)−1 (9)
C ′TMdiag(γ)C ′ is invertible as long as at least n soft constraints are on the quadratic segment (i.e., active), which is the necessary condition to fix a particular optimal point n inRn. With such solution, we can train our prediction model with stochastic gradient descent (SGD). For each batch of problem instances, we first solve optimization problems numerically using solvers like Gurobi to get the matrix M and U , and then calculate gradients with the analytical solution. The parameters of the prediction model are updated by such gradients. The sketch of our algorithm is outlined in Appendix C.

heading: 4 Applications and Experiments

text:
We apply and evaluate our approach on the three problems described in Section 2, i.e.,linear programming, quadratic programming, and asymmetric soft constraint minimization. These problems are closely related to three applications respectively: synthetic linear programming, portfolio optimization, and resource provisioning, which are constructed using synthetic or real-world datasets. The detailed derivation of gradients for each application can be found in Appendix D.
In our experiments, the performance is measured in regret, which is the difference between the objective value when solving optimization over predicted parameters and the objective value when solving optimization over actual parameters. For each experiment, we choose two generic two-stage methods with L1-loss and L2-loss, as well as decision-focused methods for comparison baselines. We choose both SPO+[10] and DF proposed by Wilder et al. [9] for synthetic linear programming and DF only for portfolio optimization,4 as the former is specially designed for for linear objective. For resource provisioning, we use a problem-specific weighted L1 loss, as both SPO+ and DF are not designed for gradients with respect to variables in the soft constraints. All reported results for each method are obtained by averaging on 15 independent runs with different random seeds.
As real-world data is more lenient than extreme cases, in practice we use a much lower empirical bound than the upper bound proved in section 3.1., e.g., constants of around 20 and 5 √ n where n is the number of dimensions of decision variables. One rule of thumb is to start from a reasonable constant or a constant times √ n, where such "reasonable constant" is the product of a constant factor (e.g. 5− 10) and a roughly estimated upper bound of ||θ||2 (which corresponds to E in our bounds) with specific problem settings; then alternately increase the constant and time an extra √ n while resetting the constant until the program stops diverging, and the hard constraints are satisfied. In our experiments, we hardly observe situations where such process goes for two or more steps.

heading: 4.1 Synthetic Linear Programming

text:
Problem setup. The prediction dataset {(ξi, θi)}Ni=1 is generated by a general structural causal model ([21]), ensuring it is representative and consistent with physical process in nature. The programming parameters are generated for various scales in numbers of decision variables, hard constraints, and soft constraints. Full details are given in Appendix E.
4The method [3] and its variant with dimension reduction [9] have same performance in terms of regret on this problem, thus we choose the former for comparison convenience.
Experimental setup. All five methods use the same prediction model – a fully connected neural network of two hidden layers with 128 neurons for each and ReLU [22] for activation. We use AdaGrad [23] as the optimizer, with learning rate 0.01 and gradient clipped at 1e− 4. We train each method for 40 epochs, and early stop when valid performance degrades for 4 consecutive epochs. Specially, to make DF[9] work right on the non-differentiable soft constraints, we first use black-box solvers to determine whether each soft constraint is active on the optimal point, and then optimize with its local expression (i.e. 2nd-order Taylor expansion at optimal point).
Performance analysis. Our experiments cover four programming problem scales with three prediction dataset sizes. Results are summarized in Table 1. In all cases, our method performs consistently better than two-stage methods, DF and SPO+. Even for the cases with only hard constraints (i.e., the third parameter of problem size is 0), our method still has significant advantage, demonstrating its effectiveness on handling hard constraints. Surprisingly, although the main objective is linear, SPO+ often performs even worse than two-stage methods. Detailed analysis (see the appendix) shows that SPO+ quickly reaches the test optimality and then over-fits. This may be due to that, unlike our method, SPO+ loss is not designed to align with the soft constraints. This unawareness of soft constraint is also why DF is performing worse than our method, as DF is working on an optimization landscape that is non-differentiable at the boundary of soft constraints, on which the optimal point usually lies. Besides, with the increment of the samples in train data, the performance of all methods is improved significantly and the performance gap among ours and two-stage methods becomes narrow, which implies that prediction of two-stage methods becomes better and with lower biases. Even so, our method has better sample efficiency than two-stage methods.
We also investigated effect of the hyper-parameter K in our surrogate max function, detailed in the appendix. Through our experiments, K’s effect to regret is not monotonic, and its optimal value varies for different problem sizes. Interestingly,K’s effect is approximately smooth. Thus, in practice, we use simple grid search to efficiently find the best setting of K.

heading: 4.2 Portfolio Optimization

text:
Problem and experimental setup. The prediction dataset is daily price data of SP500 from 2004 to 2017 downloaded by Quandl API [24] with the same settings in [3]. We use the same fix as that in linear programming experiment to make DF[9] work with non-differentiable soft constraints, which was also used in [3] for non-convex optimization applications. Most settings are aligned with those in [3], including dataset configuration, prediction model, learning rate (0.01), optimizer (Adam), gradient clip (0.01) and number of training epochs (20). We set the number of soft constraints to 0.4 times of n, where n is the number of candidate equities. For the soft constraint αT max(Cx− d, 0), α = 15n v, where each element of v is generated randomly at uniform from (0, 1); the elements of matrix C is generated independently from {0, 1}, where the probability of 0 is 0.9 and 1 is 0.1. K is set as 100.
Performance analysis. Table 2 summarizes the experimental results. In total, on all problem sizes (#equities), our method performs consistently and significantly better than both two-stage (L1 and L2) methods and the decision focused DF[9]. Among the three baselines, DF is significantly better than two-stage methods, similar to results in [3]. In fact, DF under this setting can be viewed as a variant of our method with infinite K and no conversion of softening ∑ i xi = 1. The comparison to DF also demonstrates the advantage of our method on processing such non-differentiable cases against the simple 2nd-order Taylor expansion. Besides, with the increment of the number of equities, regrets of all methods decease, which indicates that for the constraint ∑ i xi = 1, larger number of equities brings smaller entries of x on average (with the presence of Q, there are many non-zero entries of x), lowering the impact of prediction error for any single entry.

heading: 4.3 Resource Provisioning

text: Problem setup. We use ERCOT energy dataset [25], which contains hourly data of energy output from 2013 to 2018, 52535 data points in total. We use the last 20% samples for test. We aim to predict the matrix C ∈ R24×8, the loads of 24 hours in 8 regions. The decision vairable x is 8-dimensional, and d = 0.5× 1 + 0.1N(0, 1). We test five sets of (α1, α2), with α1/α2 ranging from 100 to 0.01. Experimental setup. We use AdaGrad with learning rate of 0.01, and clip the gradient with norm 0.01. For the prediction model, we use McElWee’s network [26] which was highly optimized for this task, with (8× 24× 77)-dimensional numerical features and embedding ones as input. Performance analysis. Table 3 shows the experimental results. The absolute value of regret differs largely across different ratios of α1/α2. Our method is better than other methods, except for α1/α2 = 1, where the desired objective is exactly L1-loss and thus L1 performs the best. Interestingly, compared to L1/L2, the Weighted L1 performs better when α1/α2 > 1, but relatively worse otherwise. This is probably due to the dataset’s inherent sample bias (e.g., asymmetric distribution and occasional peaks), which causes the systematic bias (usually underestimation) of the prediction model. This bias exacerbates, when superposed with weighted penalty multipliers which encourage the existing bias to fall on the wrong side. Besides, the large variance for weighted L1 at α1/α2 = 0.01 is caused by a pair of outliers.

heading: 5 Related Work

text:
Differentiating argmin/argmax through optimality conditions. For convex optimization problems, the KKT conditions map coefficients to the set of solutions, and thus can be differentiated for argmin using implicit function theorem. Following this idea, existing work developed implicit layers of argmin in neural network, including OptNet [13] for quadratic programs (QP) problems and CVXPY [14] for more general convex optimization problems. Further with linear relaxation and
QP regularization, Wilder et al. derived an end-to-end framework for combinatorial programs [9], which accelerates the computation by leverage the low-rank properties of decision vectors [3], and is further extended to mixed integer linear programs in MIPaaL [27]. Besides, for the relaxed LP problems, instead of differentiating KKT conditions, IntOpt [28] proposes an interior point based approach which computes gradients by differentiating homogeneous self-dual formulation.
Optimizing surrogate loss functions. Elmachtoub and Grigas [10] proposed a convex surrogate loss function, namely SPO+, measuring the decision error induced by a prediction, which can handle polyhedral, convex and mixed integer programs with linear objectives. TOPNet [29] proposes a learned surrogate approach for exotic forms of decision loss functions, which however is hard to generalize to handle constrained programs.
Differentiating argmin is critical for gradient methods to optimize decision-focused prediction models. Many kinds of efforts, including regularization for specific problems (e.g., differentiable dynamic programming [30], differentiable submodular optimization [31]), reparameterization [32], perturbation [33] and direct optimization ([12]), are spent for optimization with discrete or continuous variables and still actively investigated.
As a comparison, our work proposes a surrogate loss function for constrained linear and quadratic programs extended with soft constraints, where the soft constraints were not considered principally in previous work. Also, unlike OptNet [13] and CVXPY [15], our method does not need to solve KKT conditions. Instead, by adding reasonable costs for infeasibility, we convert the constrained optimization problem into an unconstrained one while keeping the same solution set, and then derive the required Jacobian analytically. To some degree, we reinvent the exact function [34] in prediction+optimization.

heading: 6 Conclusion

text: In this paper, we have proposed a novel surrogate objective framework for prediction+optimization problems on linear and semi-definite negative quadratic objectives with linear soft constraints. The framework gives the theoretical bounds on constraints’ multipliers, and derives the closed-form solution as well as their gradients with respect to problem parameters required to predict by a model. We first convert the hard constraints into soft ones with reasonably large constant multipliers, making the problem unconstrained, and then optimize a piecewise surrogate locally. We apply and empirically validate our method on three applications against traditional two-stage methods and other end-to-end decision-focused methods. We believe our work is an important enhancement to the current prediction+optimization toolbox. There are two directions for the future work: one is to seek solutions which can deal with hard constraint parameters with negative entries, and the other is to develop the distributional prediction model rather than existing point estimation, to improve robustness of current prediction+optimization methods.

title: A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints


summaries: The paper proposes Dropout Graph Neural Networks (DropGNNs), an approach that utlizes dropout in a way that allows GNNs to be more expressive. In DropGNN, multiple runs  are conducted where, in each run, the nodes of the graph are dropped out with a certain small probability and passed through a  GNN to produce a distinct embedding. The embeddings of the multiple runs are aggregated (with a sum) after a non-linear  transformation of the node features. DropGNNs achieve competitive results on synthetic and real-world datasets.

summaries: This paper proposes DropGNN, a novel technique for improving the expressive power of graph neural networks. DropGNN is simple. It removes nodes randomly (even in test time unlike dropout) and aggregates the results of several runs. This paper provides some examples and theoretical results that show when DropGNN improves its expressive power compared to vanilla GNN.

summaries: The authors propose DropGNN, a GNN exension where multiple forward passes of the model are aggregated. In each of the passes, each node in the graph is dropped with probability $p$ independently. Aggregating a sufficiently large number of dropout combinations effectively breaks symmetries that lead to traditional GNNs to not be able to distinguish between certain neighborhoods. The authors present theoretical results that DropGNNs can distinguish neighborhoods that traditional GNNs (e.g., GIN) cannot. The authors evaluate their method on both synthetic and real-world datasets.

summaries: The paper suggests a method to the GNN toolbox. The proposed method applies multiple, independent evaluations of a graph, each including random dropout applied to the graph nodes. The different evaluations are then aggregated to a single classification/regression result.

abstractText: This paper studies Dropout Graph Neural Networks (DropGNNs), a new approach that aims to overcome the limitations of standard GNN frameworks. In DropGNNs, we execute multiple runs of a GNN on the input graph, with some of the nodes randomly and independently dropped in each of these runs. Then, we combine the results of these runs to obtain the final result. We prove that DropGNNs can distinguish various graph neighborhoods that cannot be separated by message passing GNNs. We derive theoretical bounds for the number of runs required to ensure a reliable distribution of dropouts, and we prove several properties regarding the expressive capabilities and limits of DropGNNs. We experimentally validate our theoretical findings on expressiveness. Furthermore, we show that DropGNNs perform competitively on established GNN benchmarks.

authors:
R. Abboud
İ.İ. Ceylan
M. Grohe
T. Lukasiewicz

title: The surprising power of graph neural networks with random node initialization

venue: arXiv preprint arXiv:2010.01179,

authors:
J. Atwood
D. Towsley

title: Diffusion-convolutional neural networks

venue: In Advances in neural information processing systems,

authors:
P.W. Battaglia
J.B. Hamrick
V. Bapst
A. Sanchez-Gonzalez
V. Zambaldi
M. Malinowski
A. Tacchetti
D. Raposo
A. Santoro
R. Faulkner

title: Relational inductive biases, deep learning, and graph networks

venue: arXiv preprint arXiv:1806.01261,

authors:
A. Bojchevski
J. Klicpera
S. Günnemann

title: Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more

venue: In Proceedings of the 37th International Conference on Machine Learning,

authors:
J. Bruna
W. Zaremba
A. Szlam
Y. LeCun

title: Spectral networks and locally connected networks on graphs

venue: In 2nd International Conference on Learning Representations,

authors:
Z. Chen
L. Chen
S. Villar
J. Bruna

title: On the equivalence between graph isomorphism testing and function approximation with gnns

venue: Advances in neural information processing systems,

authors:
J. Cohen
E. Rosenfeld
Z. Kolter

title: Certified adversarial robustness via randomized smoothing

venue: In Proceedings of the 36th International Conference on Machine Learning,

authors:
M. Defferrard
X. Bresson
P. Vandergheynst

title: Convolutional neural networks on graphs with fast localized spectral filtering

authors:
W. Feng
J. Zhang
Y. Dong
Y. Han
H. Luan
Q. Xu
Q. Yang
E. Kharlamov
J. Tang

title: Graph random neural networks for semi-supervised learning on graphs

authors:
M. Fey
J.E. Lenssen

title: Fast graph representation learning with pytorch geometric

venue: arXiv preprint arXiv:1903.02428,

authors:
V. Garg
S. Jegelka
T. Jaakkola

title: Generalization and representational limits of graph neural networks

authors:
J. Gilmer
S.S. Schoenholz
P.F. Riley
O. Vinyals
G.E. Dahl

title: Neural message passing for quantum chemistry

venue: In International Conference on Machine Learning (ICML),

authors:
W. Hamilton
Z. Ying
J. Leskovec

title: Inductive representation learning on large graphs

title: A survey of the reconstruction conjecture

venue: Graphs and Combinatorics,

authors:
W. Hu
B. Liu
J. Gomes
M. Zitnik
P. Liang
V. Pande
J. Leskovec

title: Strategies for pre-training graph neural networks

authors:
S. Ioffe
C. Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

venue: In International conference on machine learning,

authors:
D.P. Kingma
J. Ba

title: Adam: A method for stochastic optimization

venue: In ICLR (Poster),

authors:
T.N. Kipf
M. Welling

title: Semi-supervised classification with graph convolutional networks

venue: In International Conference on Learning Representations ICLR,

authors:
J. Klicpera
J. Groß
S. Günnemann

title: Directional message passing for molecular graphs

venue: In International Conference on Learning Representations,

title: What graph neural networks cannot learn: depth vs width

venue: In 8th International Conference on Learning Representations,

authors:
H. Maron
H. Ben-Hamu
H. Serviansky
Y. Lipman

title: Provably powerful graph networks

venue: arXiv preprint arXiv:1905.11136,

authors:
C. Morris
M. Ritzert
M. Fey
W.L. Hamilton
J.E. Lenssen
G. Rattan
M. Grohe

title: Weisfeiler and leman go neural: Higher-order graph neural networks

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
M. Niepert
M. Ahmed
K. Kutzkov

title: Learning convolutional neural networks for graphs

authors:
A. Paszke
S. Gross
F. Massa
A. Lerer
J. Bradbury
G. Chanan
T. Killeen
Z. Lin
N. Gimelshein
L. Antiga

title: Pytorch: An imperative style, high-performance deep learning library

venue: arXiv preprint arXiv:1912.01703,

authors:
R. Ramakrishnan
P.O. Dral
M. Rupp
O.A. Von Lilienfeld

title: Quantum chemistry structures and properties of 134 kilo molecules

venue: Scientific data,

authors:
Y. Rong
W. Huang
T. Xu
J. Huang

title: Dropedge: Towards deep graph convolutional networks on node classification

authors:
A. Sanchez-Gonzalez
J. Godwin
T. Pfaff
R. Ying
J. Leskovec
P. Battaglia

title: Learning to simulate complex physics with graph networks

venue: In International Conference on Machine Learning,

authors:
R. Sato
M. Yamada
H. Kashima

title: Approximation ratios of graph neural networks for combinatorial problems

venue: In Neural Information Processing Systems (NeurIPS),

title: Random features strengthen graph neural networks

venue: In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM),

authors:
F. Scarselli
M. Gori
A.C. Tsoi
M. Hagenbuchner
G. Monfardini

title: The graph neural network model

venue: IEEE Transactions on Neural Networks,

authors:
N. Shervashidze
P. Schweitzer
E.J. Van Leeuwen
K. Mehlhorn
K.M. Borgwardt

title: Weisfeiler-lehman graph kernels

venue: Journal of Machine Learning Research,

authors:
N. Srivastava
G. Hinton
A. Krizhevsky
I. Sutskever
R. Salakhutdinov

title: Dropout: a simple way to prevent neural networks from overfitting

venue: The journal of machine learning research,

authors:
P. Velickovic
G. Cucurull
A. Casanova
A. Romero
P. Liò
Y. Bengio

title: Graph attention networks

venue: In International Conference on Learning Representations (ICLR),

authors:
Z. Wu
B. Ramsundar
E.N. Feinberg
J. Gomes
C. Geniesse
A.S. Pappu
K. Leswing
V. Pande

title: Moleculenet: a benchmark for molecular machine learning

venue: Chemical science,

authors:
Z. Wu
S. Pan
F. Chen
G. Long
C. Zhang
S.Y. Philip

title: A comprehensive survey on graph neural networks

venue: IEEE Transactions on Neural Networks and Learning Systems,

authors:
K. Xu
C. Li
Y. Tian
T. Sonobe
K.-i. Kawarabayashi
S. Jegelka

title: Representation learning on graphs with jumping knowledge networks

authors:
K. Xu
W. Hu
J. Leskovec
S. Jegelka

title: How powerful are graph neural networks

authors:
P. Yanardag
S. Vishwanathan

title: Deep graph kernels

venue: In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining,

authors:
M. Zhang
Z. Cui
M. Neumann
Y. Chen

title: An end-to-end deep learning architecture for graph classification

heading: 1 Introduction

text:
Neural networks have been successful in handling various forms of data. Since some of the world’s most interesting data is represented by graphs, Graph Neural Networks (GNNs) have achieved state-of-the-art performance in various fields such as quantum chemistry, physics, or social networks [12; 27; 18]. On the other hand, GNNs are also known to have severe limitations and are sometimes unable to recognize even simple graph structures.
In this paper, we present a new approach to increase the expressiveness of GNNs, called Dropout Graph Neural Networks (DropGNNs). Our main idea is to execute not one but multiple different runs of the GNN. We then aggregate the results from these different runs into a final result.
In each of these runs, we remove (“drop out”) each node in the graph with a small probability p. As such, the different runs of an episode will allow us to not only observe the actual extended neighborhood of a node for some number of layers d, but rather to observe various slightly perturbed versions of this d-hop neighborhood. We emphasize that this notion of dropouts is very different from the popular dropout regularization method; in particular, DropGNNs remove nodes during both training and testing, since their goal is to observe a similar distribution of dropout patterns during training and testing.
This dropout technique increases the expressive power of our GNNs dramatically: even when two distinct d-hop neighborhoods cannot be distinguished by a standard GNN, their dropout variants (with a few nodes removed) are already separable by GNNs in most cases. Thus by learning to identify the dropout patterns where the two d-hop neighborhoods differ, DropGNNs can also distinguish a wide variety of cases that are beyond the theoretical limits of standard GNNs.
Our contributions. We begin by showing several example graphs that are not distinguishable in the regular GNN setting but can be easily separated by DropGNNs. We then analyze the theoretical properties of DropGNNs in detail. We first show that executing Õ(γ) different runs is often already
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
sufficient to ensure that we observe a reasonable distribution of dropouts in a neighborhood of size γ. We then discuss the theoretical capabilities and limitations of DropGNNs in general, as well as the limits of the dropout approach when combined with specific aggregation methods.
We validate our theoretical findings on established problems that are impossible to solve for standard GNNs. We find that DropGNNs clearly outperform the competition on these datasets. We further show that DropGNNs have a competitive performance on several established graph benchmarks, and they provide particularly impressive results in applications where the graph structure is really a crucial factor.

heading: 2 Related Work

text:
GNNs apply deep learning to graph-structured data [30]. In GNNs, every node has an embedding that is shared over multiple iterations with its neighbors. This way nodes can gather their neighbors’ features. In recent years, many different models have been proposed to realize how the information between nodes is shared [35]. Some approaches take inspiration from convolution [23; 8; 13], others from graph spectra [18; 5], others from attention [33], and others extend previous ideas of established concepts such as skip connections [36].
Principally, GNNs are limited in their expressiveness by the Weisfeiler-Lehman test (WL-test) [37], a heuristic to the graph isomorphism problem. The work of [37] proposes a new architecture, Graph Isomoprhism Networks (GIN), that is proven to be exactly as powerful as the WL-test. However, even GINs cannot distinguish certain different graphs, namely those that the WL-test cannot distinguish. This finding [11] motivated more expressive GNN architectures. These improvements follow two main paths.
The first approach augments the features of nodes or edges by additional information to make nodes with similar neighborhoods distinguishable. Several kinds of information have been used: inspired from distributed computing are port numbers on edges [28], unique IDs for nodes [20], or random features on nodes [29; 1]. Another idea is to use angles between edges [19] from chemistry (where edges correspond to electron bonds).
However, all of these approaches have some shortcomings. For ports and angles, there are some simple example graphs that still cannot be distinguished with these extensions [11]. Adding IDs or random features helps during training, but the learned models do not generalize: GNNs often tend to overfit to the specific random values in the training set, and as such, they produce weaker results on unseen test graphs that received different random values. In contrast to this, DropGNNs observe a similar distribution of embeddings during training and testing, and hence they also generalize well to test set graphs.
The second approach exploits the fact that running the WL-test on tuples, triples, or generally ktuples keeps increasing its expressiveness. Thus a GNN operating on tuples of nodes has higher expressiveness than a standard GNN [22; 21]. However, the downside of this approach is that even building a second-order graph blows up the graph quadratically. The computational cost quickly becomes a problem that needs to be to addressed, for example with sampling [22]. Furthermore, second-order graph creation is a global operation of the graph that destroys the local semantics induced by the edges. In contrast to this, DropGNN can reason about graphs beyond the WL-test with only a small overhead (through run repetition), while also keeping the local graph structure intact.
Our work is also somewhat similar to the randomized smoothing approach [7], which has also been extended to GNNs recently [4]. This approach also conducts multiple runs on slightly perturbed variants of the data. However, in randomized smoothing, the different embeddings are combined in a smoothing operation (e.g. majority voting), which specifically aims to get rid of the atypical perturbed variants in order to increase robustness. In contrast to this, the main idea of DropGNNs is exactly to find and identify these perturbed special cases which are notably different from the original neighborhood, since these allow us to distinguish graphs that otherwise seem identical.
Finally, we note that removing nodes is a common tool for regularization in deep neural networks, which has also seen use in GNNs [26; 9]. However, as mentioned before, this is a different dropout concept where nodes are only removed during training to reduce the co-dependence of nodes.

heading: 3 DropGNN

heading: 3.1 About GNNs

text:
Almost all GNN architectures [33; 18; 37; 8; 35; 13; 36] follow the message passing framework [12; 3]. Every node starts with an embedding given by its initial features. One round of message passing has three steps. In the first MESSAGE step, nodes create a message based on their embedding and send this message to all neighbors. Second, nodes AGGREGATE all messages they receive. Third, every node UPDATEs its embedding based on its old embedding and the aggregated messages. One such round corresponds to one GNN layer. Usually, a GNN performs d rounds of message passing for some small constant d. Thus, the node’s embedding in a GNN reflects its features and the information within its d-hop neighborhood. Finally, a READOUT method translates these final embeddings into predictions. Usually, MESSAGE, AGGREGATE, UPDATE and READOUT are functions with learnable parameters, for instance linear layers with activation functions.
This GNN paradigm is closely related to the WL-test for a pair of graphs, which is an iterative color refinement procedure. In rounds 1, ..., d, each node looks at its own color and the multiset of colors of its direct neighbors, and uses a hash function to select a new color based on this information. As such, if the WL-test cannot distinguish two graphs, then a standard GNN cannot distinguish them either: intuitively, the nodes in these graphs receive the same messages and create the same embedding in each round, and thus they always arrive at the same final result.

heading: 3.2 Idea and motivation

text:
The main idea of DropGNNs is to execute multiple independent runs of the GNN during both training and testing. In each run, every node of the GNN is removed with probability p, independently from all other nodes. If a node v is removed during a run, then v does not send or receive any messages to/from its neighbors and does not affect the remaining nodes in any way. Essentially, the GNN behaves as if v (and its incident edges) were not present in the graph in the specific run, and no embedding is computed for v in this run (see Figure 1 for an illustration).
Over the course of multiple runs, dropouts allow us to not only observe the d-hop neighborhood around any node u, but also several slightly perturbed variants of this d-hop neighborhood. In the different runs, the embedding computed for umight also slightly vary, depending on which node(s) are missing from its d-hop neighborhood in a specific run. This increases the expressive power of GNNs significantly: even when two different d-hop neighborhoods cannot be distinguished by standard GNNs, the neighborhood variants observed when removing some of the nodes are usually still remarkably different. In Section 3.4, we discuss multiple examples for this improved expressiveness.
Our randomized approach means that in different runs, we will have different nodes dropping out of the GNN. As such, the GNN is only guaranteed to produce the same node embeddings in two runs if we have exactly the same subset of nodes dropping out. Given the d-hop neighborhood of a node u, we will refer to a specific subset of nodes dropping out as a dropout combination, or more concretely as a k-dropout in case the subset has size k.
In order to analyze the d-hop neighborhood of u, the reasonable strategy is to use a relatively small dropout probability p: this ensures that in each run, only a few nodes are removed (or none at all), and
thus the GNN will operate on a d-hop neighborhood that is similar to the original neighborhood of u. As a result, 1-dropouts will be frequent, while for a larger k, observing a k-dropout will be unlikely.
To reduce the effect of randomization on the final outcome, we have to execute multiple independent runs of our GNN; we denote this number of runs by r. For a successful application of the dropout idea, we have to select r large enough to ensure that the set of observed dropout combinations is already reasonably close to the actual probability distribution of dropouts. In practice, this will not be feasible for k-dropouts with large k that occur very rarely, but we can already ensure for a reasonably small r that e.g. the frequency of each 1-dropout is relatively close to its expected value.

heading: 3.3 Run aggregation

text:
Recall that standard GNNs first compute a final embedding for each node through d layers, and then they use a READOUT method to transform this into a prediction. In DropGNNs, we also need to introduce an extra phase between these two steps, called run aggregation.
In particular, we execute r independent runs of the d-layer GNN (with different dropouts), which altogether produces r distinct final embeddings for a node u. Hence we also need an extra step to merge these r distinct embeddings into a single final embedding of u, which then acts as the input for the READOUT function. This run aggregation method has to transform a multiset of embeddings into a single embedding; furthermore, it has to be a permutation-invariant function (similarly to neighborhood aggregation), since the ordering of different runs carries no meaning.
We note that simply applying a popular permutation-invariant function for run aggregation, such as sum or max, is often not expressive enough to extract sufficient information from the distribution of runs. Instead, one natural solution is to first apply a transformation on each node embedding, and only execute sum aggregation afterward. For example, a simple transformation x → σ (Wx+ b), where σ denotes a basic non-linearity such as a sigmoid or step function, is already sufficient for almost all of our examples and theoretical results in the paper.

heading: 3.4 Motivational examples

text:
We discuss several examples to demonstrate how DropGNNs are more expressive than standard GNNs. We only outline the intuitive ideas behind the behavior of the DropGNNs here; however, in Appendix A, we also describe the concrete functions that can separate each pair of graphs.
Example 1. Figure 2a shows a fundamental example of two different graphs that cannot be distinguished by the 1-WL test, consisting of cycles of different length. This example is known to be hard for extended GNNs variants: the two cases cannot even be distinguished if we also use port numbers or angles between the edges [11].
The simplest solution here is to consider a GNN with d = 2 layers; this already provides a very different distribution of dropouts in the two graphs. For example, the 8-cycle has 2 distinct 1-dropouts where u retains both of its direct neighbors, but it only has 1 neighbor at distance 2; such a situation is not possible in the 4-cycle at all. Alternatively, the 4-cycle has a 1-dropout case with probability p · (1− p)2 where u has 2 direct neighbors, but no distance 2 neighbors at all; this only happens for a 2-dropout in the 8-cycle, i.e. with a probability of only p2 · (1 − p)2. With appropriate weights, a GNN can learn to recognize these situations, and thus distinguish the two cases.
Example 2. Figure 2b shows another example of two graphs that cannot be separated by a WL test; note that node features simply correspond to the degrees of the nodes. From an algorithmic perspective, it is not hard to distinguish the two graphs from specific 1-dropout cases. Let u and v denote the two gray nodes in the graphs, and consider the process from u’s perspective. In both graphs, u can recognize if v is removed in a run since u does not receive a “gray” message in the first round. However, the dropout of v has a different effect in the two graphs later in the process: in the right-hand graph, it means that there is no gray neighbor at a 3-hop distance from u, while in the left-hand graph, u will still see a gray node (itself) in a 3-hop distance.
Thus by identifying the 1-dropout of v, an algorithm can distinguish the two graphs: if we observe runs where u receives no gray message in the first round, but it receives an (aggregated) gray message
in the third round, then u has the left-hand neighborhood. This also means that a sufficiently powerful GNN which is equivalent to the 1-WL test can also separate the two cases.
Example 3. Note that using a sum function for neighborhood aggregation is often considered a superior choice to mean, since u cannot separate e.g. the two cases shown in Figure 2c with mean aggregation [37]. However, the mean aggregation of neighbors also has some advantages over sum; most notably, it the computed values do not increase with the degree of the node.
We show that dropouts also increase the expressive power of GNNs with mean aggregation, thus possibly making mean aggregation a better choice in some applications. In particular, a DropGNN with mean aggregation is still able to separate the two cases on Figure 2c.
Assume that the two colors in the figure correspond to feature values of 1 and −1, and let p = 14 . In the left-hand graph, there is a 1-dropout where u ends up with a single neighbor of value 1; hence mean aggregation yields a value of 1 with probability 14 · 3 4 ≈ 0.19 in each run. However, in the right-hand graph, the only way to obtain a mean of 1 is through a 2-dropout or some 3-dropouts; one can calculate that the total probability of these is only 0.06 (see Appendix A). If we first transform all other values to 0 (e.g. with σ(x− 0.5), where σ is a step function), then run aggregation with mean or sum can easily separate these cases. Note that if we apply a more complex transformation at run aggregation, then separation is even much easier, since e.g. the mean value of 0.33 can only appear in the right-hand graph.

heading: 4 Theoretical analysis

heading: 4.1 Required number of runs

text:
We analyze DropGNNs with respect to the neighborhood of interest around a node u, denoted by Γ. That is, we select a specific region around u, and we want to ensure that the distribution of dropout combinations in this region is reasonably close to the actual probabilities. This choice of Γ then determines the ideal choice of p and r in our DropGNN.
One natural choice is to select Γ as the entire d-hop neighborhood of u, since a GNN will always compute its final values based on this region of the graph. Note that even for this largest possible Γ, the size of this neighborhood γ := |Γ| does not necessarily scale with the entire graph. That is, input graphs in practice are often sparse, and we can e.g. assume that their node degrees are upper bounded by a constant; this is indeed realistic in many biological or chemical applications, and also a frequent assumptions in previous works [28]. In this case, having d = O(1) layers implies that γ is also essentially a constant, regardless of the size of the graph.
However, we point out that Γ can be freely chosen as a neighborhood of any specific size. That is, even if a GNN aggregates information within a distance of d = 5 layers, we can still select Γ to denote, for example, only the 2-hop neighborhood of u. The resulting DropGNN will still compute a final node embedding based on the entire 5-hop neighborhood of u; however, our DropGNN will now only ensure that we observe a reasonable distribution of dropout combinations in the 2-hop neighborhood of u.
In this sense, the size γ is essentially a trade-off hyperparameter: while a smaller γ will require a smaller number of runs r until the distribution of dropout combinations stabilizes, a larger γ allows us to observe more variations of the region around u.
1-complete dropouts. From a strictly theoretical perspective, choosing a sufficiently large r always allows us to observe every possible dropout combination. However, since the number of combinations is exponential in γ, this approach is not viable in practice (see Appendix B for more details).
To reasonably limit the number of necessary runs, we focus on the so-called 1-complete case: we want to have enough runs to ensure that at least every 1-dropout is observed a few times. Indeed, if we can observe each variant of Γ where a single node is removed, then this might already allow a sophisticated algorithm to reconstruct a range of useful properties of Γ. Note that in all of our examples, a specific 1-dropout was already sufficient to distinguish the two cases.
For any specific node v ∈ Γ, the probability of a 1-dropout for v is p · (1− p)γ in a run (including the probability that u is not dropped out). We apply the p value that maximizes the probability of such a 1-dropout; a simple differentiation shows that this maximum is obtained at p∗ = 11+γ .
This choice of p also implies that the probability of observing a specific 1-dropout in a run is
1 1 + γ · ( γ 1 + γ )γ ≥ 1 1 + γ · 1 e .
Hence if we execute r ≥ e · (γ + 1) = Ω(γ) runs, then the expected number of times we observe a specific 1-dropout (let us denote this by E1) is at least E1 ≥ r · 1e · 1 1+γ ≥ 1.
Moreover, one can use a Chernoff bound to show that after Ω(γ log γ) runs, the frequency of each 1-dropout is sharply concentrated around E1. This also implies that we indeed observe each 1-dropout at least once with high probability.
For a more formal statement, let us consider a constant δ ∈ [0, 1] and an error probability 1t < 1. Also, given a node v ∈ Γ (or subset S ⊆ Γ), let Xv (or XS) denote the number of times this 1-dropout (|S|-dropout) occurs during our runs.
Theorem 1 If r ≥ Ω (γ log γt), then with a probability of 1 − 1t , it holds that for each v ∈ Γ, we have Xv ∈ [ (1−δ) · E1 , (1+δ) · E1 ].
With slightly more runs, we can even ensure that each k-dropout for k ≥ 2 happens less frequently than 1-dropouts. In this case, it already becomes possible to distinguish 1-dropouts from multipledropout cases based on their frequency.
Theorem 2 If r ≥ Ω ( γ2 + γ log γt ) , then with a probability of 1− 1t it holds that
• for each v ∈ Γ, we have Xv ∈ [ (1−δ) · E1 , (1+δ) · E1 ],
• for each S ⊆ Γ with |S| ≥ 2, we have XS < (1−δ) · E1.
Since the number of all dropout combinations is in the magnitude of 2γ , proving this bound is slightly more technical. We discuss the proofs of these theorems in Appendix B.
Note that in sparse graphs, where γ is essentially a constant, the number of runs described in Theorems 1 and 2 is also essentially a constant; as such, DropGNNs only impose a relatively small (constant factor) overhead in this case.
Finally, note that these theorems only consider the dropout distribution around a specific node u. To ensure the same properties for all n nodes in the graph simultaneously, we need to add a further factor of n within the logarithm to the number of necessary runs in Theorems 1 and 2. However, while this is only a logarithmic dependence on n, it might still be undesired in practice.

heading: 4.2 Expressive power of DropGNNs

text:
In Section 3.4, we have seen that DropGNNs often succeed when a WL-test fails. It is natural to wonder about the capabilities and limits of the dropout approach in general; we study this question for multiple neighborhood aggregation methods separately.
We consider neighborhood aggregation with sum and mean in more detail; the proofs of the corresponding claims are discussed in Appendices C and D, respectively. Appendix D also discusses briefly why max aggregation does not combine well with the dropout approach in practice.
Aggregation with sum. Previous work has already shown that sum neighborhood aggregation allows for an injective GNN design, which computes a different embedding for any two neighborhoods whenever they are not equivalent for the WL-test [37]. Intuitively speaking, this means that sum aggregation has the same expressive power as a general-purpose d-hop distributed algorithm in the corresponding model, i.e. without IDs or port numbers. Hence to understand the expressiveness of DropGNNs in this case, one needs to analyze which embeddings can be computed by such a distributed algorithm from a specific (observed) distribution of dropout combinations.
It is already non-trivial to find two distinct neighborhoods that cannot be distinguished in the 1- complete case. However, such an example exists, even if we also consider 2-dropouts. That is, one can construct a pair of d-hop neighborhoods that are non-isomorphic, and yet they produce the exact same distribution of 1- and 2-dropout neighborhoods in a d-layer DropGNN.
Theorem 3 There exists a pair of neighborhoods that cannot be distinguished by 1- and 2-dropouts.
We illustrate a simpler example for only 1-dropouts in Figure 3. For a construction that also covers the case of 2-dropouts, the analysis is more technical; we defer this to Appendix C.
We note that even these more difficult examples can be distinguished with our dropout approach, based on their k-dropouts for larger k values. However, this requires an even higher number of runs: we need to ensure that we can observe a reliable distribution even for these many-node dropouts.
On the other hand, our dropout approach becomes even more powerful if we combine it e.g. with the extension by port numbers introduced in [28]. Intuitively speaking, port numbers allow an algorithm to determine all paths to the removed node in a 1-dropout, which in turn allows us to reconstruct the entire d-hop neighborhood of u. As such, in this case, 1-complete dropouts already allow us to distinguish any two neighborhoods.
Theorem 4 In the setting of Theorem 1, a DropGNN with port numbers can distinguish any two non-isomorphic d-hop neighborhoods.
Finally, we note that the expressive power of DropGNNs in the 1-complete case is closely related to the graph reconstruction problem, which is a major open problem in theoretical computer science since the 1940s [14]. We discuss the differences between the two settings in Appendix C.
Aggregation with mean. We have seen in Section 3.4 that even with mean aggregation, DropGNNs can sometimes distinguish 1-hop neighborhoods (that is, multisets S1 and S2 of features) which look identical to a standard GNN. One can also prove in general that a similar separation is possible in various cases, e.g. whenever the two multisets have the same size.
Lemma 1 Let S1 6= S2 be two multisets of feature vectors with |S1| = |S2|. Then S1 and S2 can be distinguished by a DropGNN with mean neighborhood aggregation.
However, in the general case, mean aggregation does not allow us to separate any two multisets based on 1-dropouts. In particular, in Appendix C, we also describe an example of multisets S1 ∩ S2 = ∅ where the distribution of means obtained from 0- and 1-dropouts is essentially identical in S1 and S2. This implies that if we want to distinguish these multisets S1 and S2, then the best we can hope for is a more complex approach based on multiple-node dropouts.

heading: 5 Experiments

text: In all cases we extend the base GNN model to a DropGNN by running the GNN r times in parallel, doing mean aggregation over the resulting r node embedding copies before the graph readout step and then applying the base GNN’s graph readout. Additionally, an auxiliary readout head is added to produce predictions based on each individual run. These predictions are used for an auxiliary loss term which comprises 13 of the final loss. Unless stated otherwise, we set the number of runs to m and choose the dropout probability to be p = 1m , where m is the mean number of nodes in the graphs in the dataset. This is based on the assumption, that in the datasets we use the GNN will usually have the receptive field which covers the whole graph. We implement random node dropout by, in each run, setting all features of randomly selected nodes to 0. See Appendix E for more details about the experimental setup and dataset statistics. The code is publicly available1.

heading: 5.1 Datasets beyond WL

text:
To see the capabilities of DropGNN in practice we test on existing synthetic datasets, which are known to require expressiveness beyond the WL-test. We use the datasets from Sato et al. [29] that are based on 3−regular graphs. Nodes have to predict whether they are part of a triangle (TRIANGLES) or have to predict their local clustering coefficient (LCC). We test on the two counterexamples LIMITS 1 (Figure 2a) and LIMITS 2 from Garg et al. [11] where we compare two smaller structures versus one larger structure. We employ the dataset by Loukas [20] to classify graphs on containing a cycle of length 4 (4-CYCLES). We increase the regularity in this dataset by ensuring that each node has a degree of 2. Finally we experiment on circular graphs with skip links (SKIP-CIRCLES) by Chen et al. [6], where the model needs to classify if a given circular graph has skip links of length {2, 3, 4, 5, 6, 9, 11, 12, 13, 16}. For comparison, we try several other GNN modifications which increase expressiveness. For control, we run a vanilla GNN on these datasets. We then extend this base GNN with (i) ports [28] (randomly assigned), (ii) node IDs [20] (randomly permuted), and (iii) a random feature from the standard normal distribution [29]. The architecture for all GNNs is a 4-layer GIN with sum as aggregation and ε = 0. For DropGNN r = 50 runs are performed. For the SKIP-CIRCLES dataset we use a 9-layer GIN instead, as the skip links can form cycles of up to 17 hops.
We train all methods for 1, 000 epochs and then evaluate the accuracy on the training set. We then test on a new graph (with new features). We report training and testing averaged across 10 initializations in Table 1. We can see that DropGNN outperforms the competition.

heading: 5.2 Sensitivity analysis

text:
We investigate the impact of the number of independent runs on the overall accuracy. Generally, we expect an increasing number of runs to more reliably produce informative dropouts. We train with a sufficiently high number of runs (50) with the same setting as before. Now, we reevaluate DropGNN but limit the runs to a smaller number. We measure the average accuracy over 10 seeds with 10 tests each and plot this average in Figure 4 on three datasets: LIMITS 1 (Figure 4a), 4-CYCLES (Figure 4b), and TRIANGLES (Figure 4c). In all three datasets, more runs directly translate to higher accuracy.
Next, we investigate the impact of the dropout probability p. We use the same setting as before, but instead of varying the number of runs in the reevaluation, we train and test with different probabilities
1https://github.com/KarolisMart/DropGNN
p on an exponential scale from 0.01 to 0.64. We also try 0 (no dropout) and 0.95 (almost everything is dropped). Figure 5 shows the accuracy for each dropout probability, again averaged over 10 seeds with 10 tests each. Generally, DropGNN is robust to different values of p until p becomes very large.

heading: 5.3 Graph classification

text:
We evaluate and compare our modified GIN model (DropGIN) with the original GIN model and other GNN models of various expressiveness levels on real-world graph classification datasets. We use three bioinformatics datasets (MUTAG, PTC, PROTEINS) and two social networks (IMDB-BINARY and IMDB-MULTI) [38]. Following [37] node degree is used as the sole input feature for the IMDB datasets, while for the bioinformatics datasets the original categorical node features are used.
We follow the evaluation and model selection protocol described in [37] and report the 10-fold cross-validation accuracies [38]. We extend the original 4-layer GIN model described in [37] and use the same hyper-parameter selection as [37]. From Figure 5 we can see that it is usually safer to use a slightly larger p than a slightly smaller one. Due to this, we set the node dropout probability to p = 2m , where m is the mean number of nodes in the graphs in the dataset.
Our method successfully improves the results achieved by the original GIN model on the bioinformatics datasets (Table 2) and is, in general, competitive with the more complex and computationally expensive expressive GNNs. Namely, the 1-2-3 GNN [22] which has expressive power close to that of 3-WL and O(n4) time complexity, and the Provably Powerful Graph Network (PPGN) [21] which has 3-WL expressive power and O(n3) time complexity. Compared to that, our method has only O(rn) time complexity. However, we do observe, that our approach slightly underperforms the original GIN model on the IMDB-M dataset. Since the other expressive GNNs also underperform when compared to the original GIN model, it is possible that classifying graphs in this dataset rarely requires higher expressiveness. In such cases, our model can lose accuracy compared to the base GNN as many runs are required to achieve a fully stable dropout distribution.

heading: 5.4 Graph property regression

text:
We investigate how our dropout technique performs using different base GNN models on a different, graph regression, task. We use the QM9 dataset [25], which consists of 134k organic molecules. The task is to predict 12 real-valued physical quantities for each molecule. In all cases, a separate model is trained to predict each quantity. We choose two GNN models to augment: MPNN [12] and 1-GNN [22]. We set the DropGNN run count and node dropout probability the same way as done for graph classification. Following previous work [22; 21] the data is split into 80% training, 10% validation, and 10% test sets. Both DropGNN model versions are trained for 300 epochs.
From Table 3 we can see that Drop-1-GNN improves upon 1-GNN in most of the cases. In some of them, it even outperforms the much more computationally expensive 1-2-3-GNN, which uses higherorder graphs and has three times more parameters [22]. Meanwhile, DropMPNN always substantially improves on MPNN, often outperforming the Provably Powerful Graph Network (PPGN), which as you may recall scales as O(n3). This highlights the fact that while the DropGNN usually improves upon the base model, the final performance is highly dependent on the base model itself. For example, 1-GNN does not use skip connections, which might make retaining detailed information about the node’s extended neighborhood much harder and this information is crucial for our dropout technique.

heading: 6 Conclusion

text:
We have introduced a theoretically motivated DropGNN framework, which allows us to easily increase the expressive power of existing message passing GNNs, both in theory and practice. DropGNNs are also competitive with more complex GNN architectures which are specially designed to have high expressive power but have high computational complexity. In contrast, our framework allows for an arbitrary trade-off between expressiveness and computational complexity by choosing the number of rounds r accordingly.
Societal Impact. In summary, we proposed a model-agnostic architecture improvement for GNNs. We do not strive to solve a particular problem but to enhance the GNN toolbox. Therefore, we do not see an immediate impact on society. We found in our experiments that DropGNN works best on graphs with smaller degrees, such as molecular graphs. Therefore, we imagine that using DropGNN in these scenarios is interesting to explore further.

title: DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks