A Framework For Differentiable Discovery Of Graph Algorithms
Authors: Hanjun Dai
Xinshi Chen
Yu Li
Xin Gao
Le Song
Venue:  (2021)
Keywords: graph neural networks
combinatorial optimization
differentiable search
model explanation

Abstract: Recently there is a surge of interests in using graph neural networks (GNNs) to learn algorithms. However, these works focus more on imitating existing algorithms, and are limited in two important aspects: the search space for algorithms is too small and the learned GNN models are not interpretable. To address these issues, we propose a novel framework which enlarge the search space using cheap global information from tree decomposition of the graphs, and can explain the structures of the graph leading to the decision of learned algorithms. We apply our framework to three NP-complete problems on graphs and show that the framework is able to discover effective and explainable algorithms. 

Under review as a conference paper at ICLR 2021
A FRAMEWORK FOR DIFFERENTIABLE DISCOVERY OF GRAPH ALGORIHTMM
A Anonymous authors
Paper under double-blind review
ABSTRACT
Recently there is a surge of interests in using graph neural networks (GNNs) learn algorithms. However, these works focus more imitating existing algo- rithms, and are limited in two important aspects: the search space for algorithms is too small and the learned GNN models are not interpretable. To address these issues, we propose novel framework which enlarge the search space using cheap global information from tree decomposition of the graphs, and can explain the structures of the graph leading to the decision of learned algorithms. We apply our framework to three NP-complete problems graphs and show that the framework is able to discover effective and explainable algorithms.
INTRODUCTION
Many graph problems such maximum cut and minimum vertex cover are NP-hard. The classi- cal algorithm design paradigm often requires significant efforts from domain experts to understand and exploit problem structures, in order come up with effective procedures. However, for more complex problems and in the presence of a family of problem instances, it is becoming increasingly challenging for human identify the problem structures and tailor algorithms. Thus there a surge of interests in recent years to use learning and differentiable search to discover graph algorithms.
In this context, GNNs have been widely used for representing and learning graph algorithms (Dai et al., 2018; Li et al., 2018). However, directly using a GNN model to define the algorithm search space may not be enough for discovering an algorithm better than existing greedy ones. Hella et al. (2015); Sato et al. (2019) have theoretically discussed the limitations of GNNs for expressing more powerful algorithms,, by bridging the connection between GNNs and distributed local algorithms. Sato et al. (2019) derived the approximation ratios of the algorithms that can be learned by GNNs, which are much worse than those of some simple algorithms (Johnson, 1974; Chlcbik & Chicbiková, 2008). Intuitively, GNNs can only capture local graph patterns, but miss out the global information, which fundamentally restricts their expressiveness power.
To enhance the capacity of GNNs and allow for a larger search space, we incorporate global infor- mation about the graph as additional features, and augment them with other node/edge features. The idea of incorporating additional features to improve the expressiveness of GNNs has been deployed in serval existing models, by adding either unique node identifiers (Donnat et al., 2018; Seo et al., 2019; Zhang al., 2020), the information of port numbering (Sato et al., 2019), or randomness (Sato et al., 2020). However, these features are added mainly to break the local symmetry of similar graph patterns, but do not add much information about the global graph properties.
Another important aspect which have largely been ignored in previous work is explaining the learned algorithm encoded in GNN. Many previous works focus on the ability of GNNs to imitate existing graph algorithms, without showing new algorithms are being learned. One exception is that Khalil et al. (2017) experimentally showed that GNN has discovered new algorithm for minimum vertex cover problem where the node selection policy balances between node degree and the connectivity of the graph. However, this phenomenon was just mentioned in passing, and a systematic explanation of the graph patterns leading to the algorithm decision is missing. Therefore, there is an urgent need to develop explainable graph models to understand the learned algorithm.
In this paper, we propose framework for differentiable graph algorithm discovery (DAD), fo- cusing on two important aspects of the discovery process: designing larger search space, and an effective explainer model. More specifically, design a search space for graph algorithms by

---

Under review as a conference paper at ICLR 2021
Greph Newrrl Netwardo (RWW))
Graph Explaier Model
Sporiis
Tree
Groph
Augnert
Dptain
Explonation
Tarat
Figure 1: DAD has components: (1) augment problem instance graph with cheap global information; (2)
learn graph neural networks with augmented graphs: (3) explain the learned GNN with graph explainer model.
augmenting GNNs with cheap global graph features. Our proposed global features are specially de- signed for learning graph algorithms. It reveals to be a simple yet effective way of enhancing the capacity of GNNs. After the GNN is sufficiently trained, we employ novel graph explainer model to figure out the structural property of the graph leading to the algorithm decision. The graph ex- plainer model allows transform the algorithm represented in continuous embedding space back to the interpretable discrete space, so that it can assist human experts in understanding the discovery.
We demonstrate our framework on three NP-hard graph algorithms: minimum vertex cover (MVC), maximum cut (Max-Cut), and minimum dominating set (MDS), Our DAD framework is able to discover graph algorithms that achieve better approximation ratios. Besides, we apply our explainer model to the learned algorithms and demonstrate some interesting and explainable patterns.
Except for methodology, we also contribute in generating new dataset. To conduct experiments on these three problems, we need to generate the solutions for the purpose of evaluation or supervised learning. We run Gurobi for around 12,000,000 core hours to generate a reasonably large set of (graph problem, solution) pairs, with varying graph sizes. It could be a very useful benchmark dataset for graph algorithm learning, which will help with future researches this area.
2 OVERVIEW
Our framework will innovate three important aspects of the graph algorithm discovery process. That is, how to design a larger search space, how to learn the GNN algorithms, and how to effectively explain the GNN after it is learned. An overview of our framework is illustrated in Figure 1.
Search space design. To allow GNNs to represent a more powerful space of algorithms, we make use of cheap global information which can be obtained in subquadratic time in the number of nodes and edges of the graph. In particular, we will find spanning trees of the original graph, and use the solutions on these trees as augmented node/edge features. In this way, the capacity of GNNs can be enhanced, and a larger space will be searched over to discovery new and effective algorithms.
Learning method. We can use either supervised or unsupervised approaches to train the GNNs. In supervised setting, the goal is to learn GNN algorithm that can imitate the results of expensive solvers but run much faster. In unsupervised setting, a larger unlabeled dataset can be used for training. and it is favorable for large graph problems where supervisions are hard to obtain.
Explainer model. We design novel graph explainer model based on an information theoretic formulation, where we train a subgraph pattern selection model such that the selected subgraph pat- terns are more influential to the decisions of the original GNN model an information theoretic sense. Furthermore, the explainer model is trained by differentiating through a blackbox combina- torial solver. Since our selection model produces discrete and interpretable local graph structures as explanations, it provides human intuition what the kind of new algorithm is learned.
DIFFERENTIABLE GRAPH ALGORITHM DISCOVERY (DAD) FRAMEWORK
3.1 BACKGROUND
We focus on three NP-hard problems in this paper: MVC, Max-Cut, and MDS. Let G (V, E, w)
be a weighted graph, where V denotes the set of nodes, E the set of edges, and w E + IR the edge weight function. Furthermore, let A and L, be the adjacent and weighted Laplacian matrices of G, and B E (0, 1) [B] be the incidence matrix, where B and B.j if (i.j) F and
2

---

Under review as a conference paper at ICLR 2021
otherwise 0. Then these problems can be formulated as integer programming (IP) problems:
miny (y; G) subject to g G) S 0 and y E {0,1)
(I)
where the objective and the set of constraints g [ gi]" are listed respectively in the table:
The optimal solutions y E {0, 10, to the above prob- lems can be viewed as binary labels on each node. There- fore, learning these solutions can be modeled binary node classification tasks. Furthermore, we will denote Y = (- Yiv]l" E {0, 1) as the random variable represent- ing the labels on the nodes, and y = ",,-.. -. =
f(y: G)
g G)
MVC Max-Cut MDS
1 1_y y y Lw y"
By
0
1 - Ay
as the values of the random variable Y.
3.2 CHEAP SOLUTIONS AS GLOBAL FEATURES
What global features could improve the expressive power of GNNs for solving graph problems? The following example motivates our design of global features.
A motivating example. While the best known algorithm for solving general linear system takes time 2 (Williams, 2012), Kelner et al. (2013) proposed a simple algorithm for solving the system L b where L is the Laplacian matrix of a graph G. in nearly-linear time. The algorithm can be summarized by major steps: (i) Find a low-stretch spanning tree T C G. and solve the problem the spanning tree Lr b to obtain an initial solution Do; (ii) Refine the initialized solution by iteratively operating on local cycles in the original graph G. The authors also formally proved the convergence and run-time guarantees for the algorithm.
Inspired by the above successful algorithm with theoretical guarantees, we generalize the idea to solve broader class of graph problems. In many graph problems, global optimal solutions can be found efficiently by algorithms such as dynamic programming if the graph is a tree. Therefore, we propose to use (i) solutions on spanning trees T G and (ii) approximate solutions of greedy algorithms on G as cheap global features to augment the original graphs. More specifically,
Given a graph G. we first find its spanning tree T C G. There are multiple ways of constructing the trees, and we can obtain spanning trees T(1).-.. ,T[,. for each graph, using the same set of n algorithms. On each tree T [k). we can apply dynamic programming (DP) based algorithms to quickly find an optimal solution on the tree, denoted by binary vector yT E 13 The tree solutions, together with the trees themselves, can be used as global features for the graph G.
glohal optimal on spanning trees, ((T(1), y (T)). ... (T(n),y"') ((")))
T(1). ... T(n)
(2)
dynamic programming
(ii We can also operate on the original graph G' to quickly obtain approximate solution by using some greedy algorithms. With a set of m greedy algorithms denoted by Gd(1), GG((m) we can obtain set of approximate solutions.
Gd (G((m) different greedy algorithms
approximate solution
{ cd(1)
, cd((m))
The tree solutions and greedy solutions will be concatenated and used as node features. Besides, each spanning tree be represented by a binary matrix T(k) E {0, 10,1]//xx10 where the (i, entry indicates whether the edge (i,j) is in the tree. These spanning trees will also be concatenated and used as edge features. Then the overall features can be denoted by
node features:
X
1 (1)
Y T()) Ga(1) y sd(m)] E (0, 13 (lx(n+m),
(4)
edge features:
Z = [1):: T(m)] E {0, Vix[V|x
(5)
In the rest of this paper, we denote X, the i-th row vector of X which corresponds to the features of node i, and Zi as the vector Jii.j. :] which corresponds to the features of the edge (i. j).
We note that these tree and greedy solution features can typically be computed in time linear in the number of nodes and edges, which will not change substantially the computational complexity of the GNN algorithms learned later. Furthermore, in our later experiments, we also show that the proposed global features can be generally applied to different graph problems and performs better than other trivially augmented features.
3

---

Under review as a conference paper at ICLR 2021
3.3 LEARNING DISTRIBUTED LOCAL GRAPH ALGORITHM
Given a graph G = (V, w) and its associated global features X and Z, GNN computes the node embeddings by iteratively aggregating the messages from neighbors:
(++1) Fo (n X (hg x; Zuj)SEN())
(6)
where h is the d-dimensional feature embedding for node E V at t-th iteration, 0 E θ are the parameters in the GNN, Fg is nonlinear propagation function, and (i)) denotes the neighbors of node i. Note that for a weighted graph we could also use the edge weights edge features. In the rest of this paper, we overload the notation Z and assume it is the concatenation of the global feature Z and the weights of the graph if provided.
After T iterations, each node embedding h will contain information about its T-hop neighbor- hood. An output layer is applied to compute the probability distribution of Y::
1 Bernouli(pp:); Pt = OutputLayer((h
ViEV.
Given the predictive distribution {p& hev, we will retrieve the binary solution fur E {0.1])ev by method of conditional expectation described in (Raghavan, 1988; Karalias & Loukas, 2020).
To learn the parameters 0 in the GNN, we consider both the supervised and unsupervised setting:
Supervised learning with ILP solvers. In the supervised setting, for each graph G. a solution y" is given by running expensive solver, and the goal is to learn GNN-based distributed local algorithm that can imitate the results of the expensive solver but runs much faster. However, one challenge is that there could exist symmetry in the solution y". For example, given feasible solution y to a Max-Cut problem, the vector - y" is an equivalent solution that gives the same cost and the same cut-set, so there could be multiple modes in the labels which will cause the 'mode- averaging" problem (Hinton et al., 1995). To overcome this problem, instead of predicting only one probability p; in Eq. 7, generate K many probability distributions, and employ the hindsight loss for each node prediction (Guzman- Riverra et al., 2012; Li et al., 2018). That is
Hindsight loss: minke(1,.-. ,Ky Ely) Pt,k)) where Pi,A OutputLayer,,("" (T)),
(8)
K could be the number of modes, and l the binary cross entropy loss.
Unsupervised learning with continuous relaxation. Generating optimal solutions for large graphs can be very expensive. Therefore, we also consider the unsupervised setting which allows the use of a large unlabeled training dataset. We will construct the unsupervised training loss based the optimization objective f and constraints g = [g..... ... 9i] of the graph problems described in Sec 3.1. The design of the loss mainly follows (Karalias & Loukas, 2020) and more details and principles can be found there. To summarize, let p iev be the predictive probability given by the GNN, our unsupervised loss defined as the following probabilistic penalty loss:
G)( EI](Y; Plo S0 where Y Bernouli(p). (9)
and / is penalty coefficient. Note that it is relaxed version of the loss proposed by Karalias & Loukas (2020), who considers the probability of the satisfaction of all constraints jointly. Here we treat the constraints separately for efficient computations. See Appendix B for more details.
Approximation ratio: As GNN is a type of distributed local algorithm, it is easy to see that admits the identify function in the function space. Given that we use the greedy algorithmic fea- tures, it is easy to see that our design space admits an algorithm that enjoys the same approximation ratio the greedy algorithm, like Oloo for MDS, or 2 for MVC and Max-Cut. This naturally achieves or improves the ratio obtained by Sato et al. (2019).
3.4 EXPLAIN THE LEARNED GNN
We simply denoted the learned GNN as Fg. To understand what algorithm is discovered in Fs, we propose novel method to explain its predictions {p. We want to find that, for each node i, which subset of nodes V C V and edges E C E are most influential to the prediction p.- Besides, the global features X and Z are induced by the solutions of spanning trees and greedy algorithms, which we denote as S = (T(1), ... T(n), Gd(1). ... Gd(m)). We are also interested in finding which trees algorithms provide more useful features for the prediction.
4

---

Under review as a conference paper at ICLR 2021
Since focus node-level predictions, our explainer is defined mapping that finds node- dependent subsets
Explainer: E: (i, - (V3,
Es.
(10)
where Vğ and E's are selected subsets of kv nodes and kÆ edges respectively, and S C is subset of ky trees/algorihmms. More precisely, we parameterize & as second GNN along with a top-K K operation, where the GNN is applied to score the set of structural elements in (V, S), and the top-K operation selects the (ky, ks) highest scoring elements. Details are provided below.
Parameterization of E. It is notable the prediction p: is computed by Fg based on the T-hop subgraph of the node and is irrelevant to nodes of distance larger than T. Therefore, when working on node i, the explainer only needs to select the influential nodes/edges from its Thoop subgraph, denoted by G(i, T) = (V(i, T), E(i, T), w). Therefore, we define explainer GNN as
Explainer GNN: F (V T), B(i, ((1))) (i) + {hī Jev(()
(11)
where (i, 7) = ( and (i,, T) == (.) are features induced by the sub- graph. Then multi-layer perceptrons (MIP) applied to define the scoring functions:
(I) Node scores: Cj- = MLP (h.) for each node j E V),
(II) Edge scores: CJ,t MLP o ([h Ex,x) for each edge (j.k) E(i,T).
(III) Feature scores: с = MLP S (Pooling ((h)) )ev(.))) where the output is (n + @
-iddimensionna vector that gives the score for features induced by the n spanning trees and the m greedy algorithms.
With the scores, the subsets (Vg, Lig. can be selected as choosing the elements with scores in top-K, for K ky.kg, kg, and ks,, respectively. In summary, the explainer model can be written as the composition of three operations
(12) Variational lower bound of mutual information. To learn the explainer Eg. we employ the learn- ing to explain (L2XX) framework in (Chen et al., 2018). In L2X, & is learned by maximizing the mutual information between the predicted label Y; and the selected subsets (Vá. S%). However, due to intractability, variational distribution parameterized by neural network Qú will be learned jointly with the explainer &s to maximize the variational lower bound of the mutual information
Parameterized Explainer: & = top-K o MLP o F.:
max E log Qv (Y, VVg, Eg, St), s.t. (V3, ES Sis) (i, V, E, Z), 0.
(13)
where the expectation taken over the predictive probability p: given by the learned GNN, over all node i in graph G and all graph G in the training set Gtrain-
Parameterization of Q. Again we will parametrize the variational distribution Qo by a third GNN
F8 (V3, E'. Z's) + (h Hiev(..)) followed by pooling and MLP:
Variational Distribution:
Q = MLP (pool
( (i, V3, E X 237)
(14)
where the features (X DTz) = H(V E S. X, Z) are induced by the selected subsets via a differentiable mapping H.
Differentiable top-K. The additional technical challenges for optimizing the variational objective in Eq. 13 is that the top-K operation in the parameterized explainer (Eq. 12) is not differentiable. More specifically, a top-K operation over the scores c,, ... CM the following integer linear programming (ILP) problem:
CM for some M is equivalent to solving
arg (00 Σ5= Cj3y
s.t. M
(15)
is easy to see that the optimal solution x; = 1 only if ej is among the top-K scores. Given this equivalence,
employ the blackbox differentiation techniques introduced by Vlastelica et al. (2019) to compute the gradient of the ILP solver, and optimize the parameters 6 in the explainer.
Discussion. Our explainer model is very different from GNNExplainer (Ying et al., 2019), which may be of independent interests in term of explainer model for GNNs. For instance, GNNExplainer optimizes the selection mask (i.e., the explainer) for individual graph, while parameterize the
5

---

Under review as a conference paper at ICLR 2021
explainer another GNN which can be applied to explain the predictions class of different graphs. Besides, the variational Q in GNNExplainer is defined to the original GNN Fe which fixed, while optimize Q over parametric family, so that optimal. Furthermore, we formulate the top- K selection as a solution to an IIP and apply a blackbox differentiation technique to optimize the explainer model, which has not been attempted in the space of explainer models before. We provide some empirical justifications in Appendix G. Discussion with other explainer models can be found in Appendix A.
method is
principled and
4 RELATED WORK
Expressiveness of GNNs for representing algorithms. GNNs have been used to learn graph algo- rithms. Some recent works have discussed the representation power of GNNs for representing graph algorithms. Xu et al. (2018) showed that GNNs are at most as powerful as the Weisfeiler-Lehme (WL) test in distinguishing graph structures. Maron et al. (2019; 2018) proposed k-GNN which can represent the results of k- WL test. Barceló et al. (2019) showed that GNNs are too weak to represent logical Boolean classifiers FOC2, and proposed to add global read-out function break this limita- tion. Focusing combinatorial problems including MDS and MVC, Sato et al. (2019) derived the approximation ratios of algorithms that GNNs can learn, and theoretically showed that adding the information of port numbering and weak-coloring can improve those approximation ratios.
Learning based graph algorithms. Empirically, several works have demonstrated the ability of GNNs for imitating existing graph algorithms. For instance, GNN is used to learn the convergent states of graph algorithms (Dai et al., 2018). imitate DP algorithms (Xu et al., 2019), and imitate individual steps and intermediate outputs of classical graph algorithms (Veličković et al., 2019). To learn a new and more effective graph algorithm, Khalil et al. (2017) combined reinforcement learning with GNNs learn greedy policies that can solve graph problems such MVC and Max- cut. Karalias & Loukas (2020) proposed an unsupervised framework for learning graph algorithms and demonstrated the results on maximum clique and local partitioning problems.
5 EXPERIMENT
In Section 5.1, we first introduce problems we are going to tackle, and the baselines we are going to compare with. Then in Section 5.2 and Section 5.3, we show the empirical approximation ratio of DAD on several synthetic and real-world datasets, and compare against several known polynomial algorithms, as well as other relevant graph neural network variants. Finally in Section 5.4, we leverage our proposed explainer to understand the learned algorithm.
5.1 EXPERIMENT SETUP
We leave the details of greedy algorithms and dynamic programming on trees in Appendix C. We first compare against some of the cheap algorithms that are also served as features. As we use the continuous relaxation in Eq. 9, we also compare with the linear/semi-definiee programming (LP/SDP) with randomized rounding for these problems:
greedy), 2Approx-Greedy(ede selection with degree greedy), 2epprox(edge selection) and LP relaxation are included.
MVC: Appooxxppoxxnodee
MDS: Greedy(sequential coverage based greedy selection) and LP relaxation are included. local adjustment), SDP and MaxSpann innannnnntoooooooon di- rectly obtained on max spanning tree, as any node assignment is a valid cut) are included.
Max-CUT:
We here include several recent works that extends GNNs with different forms of global information:
Onehot (Karalias & Loukas, 2020; Sco et al., 2019): adds one-hot encoding to random node. RandFeat (Sato et al., 2020): uses random node features to break the tie.
CPNGNNs (Sato al., 2019): leverages port numbering in GNN's message passing, together with weak 2-coloring node features. As CPNGNNS only works for graphs with bounded degree, we use the position encoding (Vaswani et al., 2017) for port number representation instead.
Raw: we simply use constant (or edge weight, when applicable) for node/edge features, which serves as the baseline for all the global information augmented GNNs.

---

Under review as a conference paper at ICLR 2021
2.0
D40 540-4 Light os
Uh Zispesx Geandy
D4o
1.40
Approimal cenation tetle
ZAcpro
Approsimat lon wate
B634
Groddy
1.35
BAD-U)
1.30
2éporta Greedy
1.6
Aetrosimatioo
VarSpariig
1,4
1:20
1.15
1.05
1.00
16-20
12-40
64-25
128-156 254-300
18:20
12-40
64-75
128-150
256-300
16.20
32:40
64-75
128-150 256-300
nodes in toin-ed grapts
nodes toan gropts
modes In traintted graphs
MVC-Barabasi Albert
MDS-Barabasi Albert
Albert
Figure 2: Test approximation ratio for different algorithms. Foreground color (darker) shows the average test ratio, while background color (lighter) shows the maximum test ratio.
1.0055
1.02
1.07
1.0
1.0200
1,06
Chicki Grdtet
1.08
Drcecct
3.0175
1.0150
Chiiiit Grahat
BareTeat
3,0020
2.0325
2.0350
2.0015
1.0075
1.0000
1.02
1.01
1.0025
1,0000
1.00
16
64.75
256
1,0000
1oddea
Erannitesl graphs
MVC-Barabasi Albert
MDS-Barabass Albert
Maxcut- Barabasi Albert
Maxcut-Barabasi
Figure 3: Test approximation ratio for GNNs with other types of global information.
5.2 QUANTITATIVE RESULTS ON RANDOM GRAPHS
Data preparation We use two random graph models, namely Erdos Renyi (ER) with edge proba- bility 0.15, and Barabasi Albert (BA) with edge attachment generate random graphs for training and test. We vary the graph sizes in { (16-20, 32-40, 16-40,, 64-75, 128-150. 256-300, 512-600, 1024-1100).
In each (problem, graph type, graph size} configuration, we generation {10k, 1k, 1k} graph in- stances for training, validation and test, respectively. We run Gurobi each instance to get the solution for evaluation or supervised training. See Appendix for more details on setup and Gurobi.
Main results: Figure shows the comparison between classical algorithms. We can see DAD leverages but goes beyond the cheap algorithms, with both supervised and unsupervised (DAD-U) learning strategies. The gain is significant regarding both the average and maximum test ratio. While the maximum ratio similar in MDS, DAD still gains advantages in average case, which is expected as we do empirical risk minimization during training. Figure 3 compares against other GNNs with global information, where our design consistently outperforms alternatives. We also tried pad the baseline GNN features with either random or constant values to match the number of parameters GNN. This doesn't 't help the baselines much which verifies that the gain of DAD not simply coming from the input size. See Appendix F.3.1 for more details.
Extrapolation: We train the models on graphs up to 300 nodes, and evaluate them up to 1100 nodes to see their extrapolation ability. We show the details in Appendix F.2, where the extrapolation results are still consistently better than the best classical baseline algorithm.
Ablation study: Here we try to understand the contributions of tree solution versus greedy solution.
We present such study in Figure 12 in appendix on the three tasks. Our main takeaways are: 1) both of the two feature families can boost GNN in most cases, comparing not using any features. 2) having multiple trees can also be helpful for MVC and MDS, as the spanning tree is not unique. 3) using both types of the features is better than either of them. This validates design principle.
Time-Solution trade-off: As exhaustive algorithms can already achieve optimal solution in finite time, want study the trade-off between time and the approximation ratio obtained by different algorithms. We show the results in figure on BA graphs with minimum 1024 nodes. For each single graph, we record down the time spent for solving and the approximation ratio, and obtain dot in the scatter plot. As Gurobi solver is an iterative process, we plot the data points every time improves the solution on the graph, and truncate. We can see DAD can achieve similar or better solution quality than what can be achieved by Gurobi, with 2 magnitudes less time.
7

---

Under review as a conference paper at ICLR 2021
3.5
Approx Ratio
BxpaU Loghi-gaees Sigeere
Approx Rakio
DMD Greedy
D40
2.4
3.5%
2.3
Approx
1.2
10
190
(ms)
(ms)
MVC-Barabasi Albert
Maxcut-Barabal Albert Figure 4: Time and approximation ratio trade-off plot for different methods.
MDS-Barabasi Albert
Table 1: Real world MVC and MDS test results.
Table Real world MAXCUT.
MVC
MDS
Optsicom-B
Optsicom-G
Data
haseline
DAD
2nd-hest haceline
2Approx
7.65e 2
7.98e
Twitter
168c
1.93
6.43e
8.43c
MaxSpanning
7.63e
7.09c-2
Githuh
1.64-1
1.09c-5
3.89
4.14e-5
SDP
8.36e
8.52e
Memetracker
181e=2
1.55e-5
1.30
7.67e
4.23e -3
1.16e 5
5.3 RESULTS ON REAL WORLD GRAPHS
Data preparation We first collect several social network datasets Twitter and Github from Morris et al. (2020). We also collect Memetracker Optsi i com and follow Khalil et al. (2017) generate training/evaluation graphs. We run MVC and MDS tasks on the social networks, and run MAXCUT on the physics(Opt ccmm) graphs. See Appendix E for more information about the dataset statistics and real-world experiment results.
We show the relative error compared to the optimal solution obtained by Gurobi in Table I and Table 2. We report DAD's performance with supervised learning setting. It still achieves the best performance on both the social networks and physics graphs, where the relative error can be several magnitudes smaller than the second best classical algorithms in some cases.
Results:
5.4 EXPLAINING LEARNED ALGORITHMS.
In this section, we use our proposed explainer to explain the learned algorithm on BA graphs. By zooming in into the important discrete substructures of the graph, we are able to find some interesting algorithmic patterns that aligns with our intuition.
Explanation with edge selection: Here we limit the number of nodes to be 5, and edges to be 10 when explaining each target node of a graph, and parameterize &g and Q using GNN with the same number of layers the target GNN. We found in figure that some nodes depict the greedy behavior, where the budget for edge explanations is mostly allocated to adjacent edges. Note that although greedy algorithm solution features, the GNN doesn't 't know about the underlying physical meaning of them. This shows that our explainer is able to re-discover the greedy algorithm.
Figure 5: Greedy-like like algorithm behavior on some nodes in MVC(left) and MDS(right) tasks. Se- lected nodes and edges are colored blue, where the target node for explanation is colored red.
Explanation with node selection: When running the explainer on a single graph with different target nodes, we found that there are several nodes appear frequently the selected subset. We call these nodes anchor nodes. We try to understand the correlation between anchor nodes and the node predictive probabilities in figure 6. We first run explainer on every node in a graph, and count how many times each node has appeared in the explanation of other nodes. The node color indicates such frequency, where the dark red has highest frequency. We can clearly see the existence of such anchors. Then we show the predicted node probability the boundary color of each node, where the dark blue has probability close to 1.0. We can see no matter how many nodes with dark blue boundaries, the anchor nodes tend distribute evenly among both high probability and low
8

---

Under review as a conference paper at ICLR 2021
Figure Anchor nodes v.s. node selection probability. From left to right: MVC, MDS, Max-
probability nodes. Our hypothesis is that GNN leverage the similarities between target node and the diverse anchor nodes to make a proper decision, where the anchors serve like landmarks in kernel methods. Such anchor node behavior is also consistent to some recent distance based designs (You al., 2019; Li al., 2020) of GNNs.
We further look at the contri- bution of different cheap global features the GNN prediction. We take the Max-Cut problem, where we use 5 global features, includ- ing Greedy and {Min, AKPW, Max, Maxx-Snanning trees. We include MaxSpanning twice the solutions symmetric and come in pairs. We can see from figure when budget is set to all the explanations select Grredy, AKPW, Ma WaxSpann innig }. despite that MaxSpanning solution has higher quality than AKPW. This shows that the explainer learns that MaxSpaning are du- plicated in identifying global information. When the budget is lim- ited our explainer still consistently identifies the best perform- ing algorithm, i.e., Greedy. From this we can learn two principles in instantiating our framework: 1) better algorithm solution generally introduces better global information; 2) having diverse algo- rithmic solutions is better than multiple similar ones.
Explanation with feature selection:
FEATURES
Greedy
Min-Sp
Max-Sp1
Budget
Budget
Figure 7: Algorithm selection
CONCLUSION
In this paper, we propose novel framework, called DAD, for differentiable discovery of graph algo- rithms. We have demonstrated that our framework search over large space of graph algorithms using GNNs and global features, and can interpret the learned algorithm by a novel explainer model. It potentially serve powerful tool to improve the existing graph-based algorithms, well as providing explanations for other downstream tasks.
REFERENCES
Noga Alon, Richard M Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. SIAM Journal on Computing, 24(1):78-100, 1995.
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus- Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wiss relevance propagation. PloS one, (01)):e0130140, 2015.
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An informationn-theortii perspective on model interpretation. arXiv preprint arXiv:1802.07814, 2018.
Miroslav Chlebík and Janka Chlebíková. Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, 206(1 1):1 2008.
Hanjun Dai, Zornisaa Kozareva, Bo Dai. Alex Smola, and Le Song. Learning steady-states of iter- ative algorithms over graphs. In International conference on machine learning, pp. 1106-1114, 2018.

---

Under review as a conference paper at ICLR 2021
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1320-13200 1329, 2018.
Abner Guzman-Rivens Dhruv Batra, and Pushmeet Kohli. Multiple choice learning: Learning to produce multiple structured outputs. In Advances in Neural Information Processing Systems, pp. 1799-1807, 2012.
Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Lu- osto, Jukka Suomela, and Jonni Virtema. Weak models of distributed computing, with connec- tions to modal logic. Distributed Computing, 28(1):31-553 2015.
Geoffrey Hinton, Peter Dayan, Brendan Frey, and Radford M Neal. The" wake-sleep" algorithm for unsupervised neural networks. Science, 268(5214): 158--1661, 1995.
David S Johnson. Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 93):2566-278 1974.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. arXiv preprint arXiv:2006. 10643, 2020.
Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu. simple, combi- natorial algorithm for solving sdd systems in nearly-linear time. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 911-920, 2013.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- 6348-6358, 2017.
Pieter-Jan Kindermans, Kristof Schütt, Klaus-Robert Müller, and Sven Dähne. Investigating the influence of noise and distractors on the interpretation of neural networks. arXiv preprint arXiv:1611.07270, 2016.
Jure Leskovec and Andrej Krevi. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.ddddd .ew./daaaddd June 2014.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding- provably more powerful gnns for structural representation learning. arXiv preprint arXiv:2009.00142, 2020.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimizztin with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp. 539-548, 2018.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. pp. 4768- 4777, 2017.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in Neural Information Pro- cessing Systems, 33, 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint
2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benehmark datasets for learning with graphs. In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www.graphlearringg.io
Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences, 37(2): 1988.
10

---

Under review as a conference paper at ICLR 2021
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144. ACM, 2016.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp. 4081- - 4090, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprini arXiv:2002.03155, 2020.
Younjoo Seo, Andreas Loukas, and Nathanaël Perraudin. Discriminative structural graph classifica- tion. arXiv preprint arXiv: 33422, 2019.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 2013.
Jost Tobias Springenberg, Alexey Dosovitskiy, Thomas Brox, and Martin Riedmiller. Striving for simplicity: The all convolutional net. arXiv preprint 141266644, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998 5998-6008, 2017.
Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execu- tion of graph algorithms. arXiv preprint arXiv:1910. 10593, 2019.
Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek. Differentiation of blackbox combinatorial solvers. arXiv preprint arXiv: 191.0119 2019.
Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith- winograd. In Proceed- ings of the forty-fourth annual ACM symposium Theory of computing, pp. 887-898, 2012.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXivv1810.000
2018.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint arXiv:1905: 13211, 2019..
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. In Advances in neural information processiin systems, pp. 9244 9255, 2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv preprint 1tl.:999000487.. 2019.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. arXiv preprint 2001:: 2020.

---

Under review as a conference paper at ICLR 2021
Appendix
A OTHER RELATED WORKS
Explainer models. Existing work on explainer models approach the problems from three directions. The first line of work use gradients of the outputs with respect to inputs to identify the salient features the inputs (Simonyan et al., 2013; Springenberg et al., 2014); The second approximates the model with simple interpretable models, such locally additive models (Bach et al.. 2015; Kindermans et al., 2016; Ribeiro et al., 2016; Lundberg & Lee, 2017); the third defines input pattern selection operators, such that the outputs of the model based the selected input patterns has large mutual informaton with the original model outputs (Chen et al., 2018; Ying et al., 2019). The difference of our explainer model compared GNNExplainer (Ying al., 2019) is discussed in Sec 3.4. The explainer we used also shares the similar merits as a concurrent work published by Luo et al. (2020), The main difference lies in the optimization technique, where the stacked Gumbel-softmax used in Luo et al. (2020), while we use a differentiable top-k operator that is more stable and casier to train in general.
B PROBABILISITC RELAXATION OF CONSTRAINTS
In main paper we mentioned that are solving the following probabiliisic relaxation of the integer programming:
Ex P(g. 0], where ~ Bernouli(p).
This can be more general for many constrained optimization problems. For example:
MVC: MVC constraint requires that each edge (i,j) has p: + P5 2 1. In the probabilistic sense, the probability violating this constraint is (1 - pt) (1 1 Pş). Thus the expected penalty would be:
B
Σ (1-Px) (1 Pu) (Z.)))
(16)
MDS:
MDS constraints are placed on nodes. The ILP constraint says Ps EyeN(y 2 1. Again, we write it in the probability sense, with the expected penalty be:
Σ (1-p)) iEV
II (1 (1-P;) JEN(()
(17)
In our experiment, we use above expected penalty to handle the hard constraints in unsupervised learning setting.
C DETAILS OF CHEAP ALGORITHMIC FEATURES
The cheap algorithm configurations are described in Table 3. For unweighted graphs the spanning
Table 3: Cheap algorithmic configurations for DAD on different problems.
Tree solutions
Greedy Algorithms
MVC
DP on random spanning tree
Node/Edge based greedy
MDS
DP random spanning tree
Node based greedy
Max-Cut
Two-coloring on max.mmin.low-stretchh spanning tree
Greedy local adjustment
trees are usually not unique, so we can use multiple tree solutions as global features for DAD. We AKPW (Alon al., 1995) for computing the low-stretch spanning tree for Max-Cut problems.
12

---

Under review as a conference paper at ICLR 2021
C.I OBTAINING TREE SOLUTIONS
Note that although these combinatorial optimization on trees easier than NP-hard, but they are still nontrivial. Here we cover the recursion of dynamic programming for these problems:
MVC: Firstly we pick a random node as root, and traverse the tree in DFS order. Suppose we use fln, 0] to denote the cover size of the subtree rooted at node n, when the node is not chosen, and [n. 1] to denote the cover size when node n. is chosen, then we have:
flm.0)
Σ f(c, 1]
eEchildin)
fln. 11
1 +
Σ min (f(c,
(18)
eEchild(n)
And the final cover size is obtained by min {frroot, 0], f'root, 1]}.
MDS: Firstly we pick random node as root, and traverse the tree in DFS order. Suppose we use f[n, 0] denote the dominant set size the subtree rooted at node n, when the node chosen; use f(n, 1] to denote the situation when n is not picked, but it has been dominated by other nodes; use f(n, 2] denote that we don't 't care about node n's situation, but its subtree should satisfy the constraint. Then we have:
f|n,0) 1
Σ
min Of, 1], 2c,
eEchildin)
[|,
Σ min U/|, [[c, 1]}
cEchildkn)
child((()
f[n,1] 1]
(19)
[fin 2] + min [f(c, 0] min (flc. Oj, flc, 1]H, otherwise
and finally the dominant size equals to min [root. 0), frooo, 1]}.
Max-Cut on tree is easy when all the edge weights are non-negative, as every tree is bipartite graph. We can perform two-coloring on this colors afterwards, we can get another equivalent solution. Although this solution is simple, it still
Max-Cut:
obtain the solution. By flipping the has nontrivial effect on obtaining the global information, weak 2-coloring on the original graph. It is known that for some problems, such information can help boost the approximation ratio of distributed local algorithms (Sato et al., 2019).
the 2-coloring solution on tree is the
D EXPERIMENTAL DETAILS
We all the experiments on cluster with 6149 nodes. In each node, there are 64 cores. To obtain the solution for evaluation or supervised training, for each graph per task, we run Gurobi on one node with the time limit as I hour. As we have three tasks, two graph models, seven graph sizes, and 12A graph instances in each category, the computational budget is 32 million core hours. In reality, we used around 12 million core hours because only the larger graph tasks can run up to hour.
Compared to that of the exact solution, the core hour consumption of the relaxed LP is neglectable. However, the SDP for Max-CUT is computationally intensive. We used cvxpy to realize it. For the larger graphs, it can take up to 40 mins to resolve one graph with 64 cores. It takes around 0.2 million core hours to obtain the SDP solutions.
We tuned the hyperparameters of GNN models for each graph category, such the number of layers and the number of spanning trees, using grid search. We run each job up to 24 hours on a 64-core node. It takes around 5 million core hours the jobs the synthetic datasets and 0.3 million core hours for the real datasets.
In total, it takes around 17.5 million core hours run all jobs.
13

---

Under review as a conference paper at ICLR 2021
Collab
Twitter
Github
Facebook
Memetracker
Optsicom
Average nodes
74.49
131.76
83.83
81.66
315.36
125.0
Average edges
2457.22
1709.32
117.32
80.58
335.68
375.0
train
3,000
583
7,635
597
10,000
10,000
valid
1,000
194
2,545
199
1,000
1,000
# test
1,000
196
2,545
199
1,000
1,000
Table 4: Real world data statistics.
Table 5; Real world MVC and MDS.
MVC
MDS
LogN-Approx
2Approx Grendy
2Approx 1.06e
LP-Relax
DAD
Greedy
LP-Relax
DAD
Collab
1.22e
8.17e
1.21e
1.28e
0
0
Facebook
0
0
0
0
5.32e
0
Twitter
1.68
1.62e
2.88e
3.84e
1.98e
8.26e
6.43e
8.42e
Github
3.61e-3
5.52c
8.23c
1.64-
1.09e 5
6,24c
3.89c-4
4.14e
Memetracker
1.81e
4.50c
7.42c
6.09c
1.55e 5
2.38e
1.30-
7.67e
E MORE REAL WORLD DATA INFORMATION
We collect of social network dataset Collab, Twitter, Github and Facebook from Morris et al. (2020), following Karalias & Loukas (2020). Each dataset comes with a set of graphs, and we split them into training/validatioonnest with ratio 6:2:2. Additionally, SNAP (Leskovec & Krevl, 2014) and Optsicom used Khalil et al. (2017). As these only have a few graphs, we use the same strategy from Khalil et al. (2017) generate graphs. Specifically, for Memetracker, we use widely-adopted Independent Cascade model and sample a diffusion cascade from the full graph with constant set and consider the largest connected component the graph as single graph instance; for Optsicom we keep the graph structures, but perturb the edges weights using Bernoulli distribution (denoted as Optsicom- B) or Gaussian distribution with zero mean and 0.1 standard deviation (denoted as Optsicom-G).
collect Memetracker graph from
See Table for the final statistics about the datasets.
For the completeness, we additionally include MVC and MDS results on Collab and Facebook datasets in Table 5. These datasets are used Karalias & Loukas (2020) but not very suitable for evaluating MVC MDS tasks, as it is easy to get exact solution with simple algorithms thest two datasets.
F MORE EXPERIMENTAL RESULTS
F. MORE IN-DISTRIBUTION GENERALIZATION RESULTS
2.0
1.8
2/2-1
Grossy
DASII
Aperodrrattie mito
3.25
2AD
1.6
ZAcpREs Greedy
JP-
Spproematon
3.20
1.4
1.3
1.1
1.0
16-20
32:60
64-75
128:100
250-300
1.0
1620
32-40
66-75
128-150
250-300
1.00
nodes traintust graphs
nodes trainiest graphs
#
modes
traf-tesst graphs
MVC-Erdos Renyi
MDS-Erdos Renyi
Maxcut-Erdos Renyi
Figure 8: Test performance comparison with other classical algorithms Erdos Renyi graphs.
In main paper we covered the comparison between DAD and other classical algorithms, as well as other types of global GNNs
Barabasi Albert graphs. Here present the results on Erdos Renyi
14

---

Under review as a conference paper at ICLR 2021
102
1.3
1.06
IMD
1.020
D40
1.0
Oneret
CINONN
Ratio wiltowrt Gumbe
1.05
2.04
RansFear
1.015
Bardfest
Wit
1.06
1.04
1.02
1.005
1.01
1.000
150 grophs
1.00
16-23
32-40
64-75
120-150 258-100
1.00
16-20
32-10
64-75
120-150 258-100
# modes tra) /ib.: /rat
nodes grapp
nodes tralnitstt graphs
MVC-ER Supervised
MDS-ER Supervised
Maxcut-ER Supervised
D6.3
D&D
1.14
BAD
Onehi:
1.05
1.06
Dreertt
CPNc101
1.25
1.30
CPNCANN
Dreten
3.10
1.12
CRIGANS
RardFeat
Ratlo
1.04
1.08
1.06
1.02
2.04
1411
1.05
1.00
1.00
1.00
rodes
nodes
nodes
MVC-ER Unsupervised
MDS-ER Unsupervised
Maxcut-ER Unsupervised
1.10
1.025
DAD
Onchet kandFent
CENGANs Orehot Ransfeet
Ratto Mrt Gumbi
CPNGCks
Randfeat
1.020
3.06
1.000
1.085
1.02
26:20
32 40
64.13
128 150
255-300
16
22
64.75
128-159 255-300
16
26:20
32 40
64-75
128 150
256-300 300 grapns
Sanrczz: grop1s
grop1c
MVC-BA Unsupervised
MDS-BA Unsupervised
Maxcut-BA Unsupervised
Figure 9: Test approximation ratio for GNNs with other types of global information.
graphs, as well as the results with unsupervised learning in figure and figure 9. We can see the proposed DAD consistently beats all other alternatives in all these settings.
F.2 MORE EXTRAPOLATION RESULTS
1.12
1.07
1.66
BAC 66-15
1.10
Agroataation mlo
2.04
DAD 00--54-35
1.05
BA0 12a 152
1.08
[AD 126-555
BAD 254
RVD 300
Ligh Agorox
1.05
24gpe Creudy
1.03
2.02
1.02
NAC-138-3 150
2.01
1.81
86P-256
Gready
16
128
256
1024
128
1024
512
1024
In praphs
grophs
grashs
MVC-Erdos Renyi
MDS-Erdoy Renyi
MaxCut-Erdos Renyi
1.10
BAD 100-14-2
DAD 32-422-2
1.010
DAD 34-75
Agraamatonn ratt
2.05
1.025
M-D-128-50
2.04
Jeth 32-43
DAD DAD-25-2
1.015
1.000
D-D-6-15
DAD-123-150
WATT
1.04
1xb-126:50
DAP 64-15
0AD-259-00 500
1.300
1.02
1.00
122
MVC-Barabasi Albert
MDS-Barabasi Albert
Maxcut- Baxcut-Barabasi Albert
Figure 10: Extrapolation results with supervised learning, compared with the best polynomial base-
line (greedy).
15

---

Under review as a conference paper at ICLR 2021
1.10
DAD-U-66 66.15
DAD-0-22 32-40
bxD-U-1620
1.30
1.25
042-J66-10
DXD-U1150
040-3-52-0
Appratmatio nloo
1.06
DAD
UAD-U-1200
D4D-J1228152
LAD-U-123-1
1.20
2.08
1.00
WT
2.04
1.04
3.02
1.00
graphs
modes
MVC-Erdos Renyi
MDS-Erdos Renyi
MaxCut- Eudos Renyi
1.10
1.000
DAD-A-G-25
8
1.025
BAD 2-00--2---10 155
04D-6-236-11 100
1.050
D4 D6.44-1295.0
D4330-30
1.000
Mrlpprox
DAD 20-20
1.045
2Asgrde-Grend Gready
1.035
DAD--13- 40
2,040
1030
1.035
1.055
Gready
125
MVC-Barabasi Albert
MDS-Barabasi Albert
MaxCut-Barabasi Albert
Figure 11: Extrapolation results with unsupervised learning, compared with the best polynomial baseline (greedy).
Here we show the extrapolation results on Erdos Renyi and Barabasi Albert graphs, where DAD is trained with supervion graphs with up to 300 nodes. We can from figure 10, DAD still extrapolates well to large graphs.
The unsupervised learning extrapolates in similar way, as seen in figure 11.
One interesting finding is that, achieves approximation ratio that less than on MDS large graphs. This indicates that the Gurobi is not capable of generating high quality solution large graphs.
Also for ER graphs, it is harder to extraplate to smaller graphs. As fix the edge probability for different sizes the graphs, the node degree distribution would shift when graph size changes. This may prevent GNNs from extrapolating well.
F.3
MORE ABLATION RESULTS
Table 6: Ablation: Real world MVC and MDS relative error.
MVC
MDS
Data
Raw
Onehot
RandFeat
DAD
Raw
Onehot
RandFeat
DAD
Collab
1.50e -4
2.05e
3.20e
1.28c
6.00e -3
Twitter
2.58e 3
2.40e 3
1
1.93e-8
8.67e
1.19e
3.37e
3.42c
Githuh
3.15e
2.86e
1.39e
1.09e
2.55e
1.22e
2.25e
4.14e
Facebook
0
0
Memetracker
7.94e
1.59e
3.49e
1.55e
1.94e
8.47e
5.21e
7.67e
Table 7: Ablation: Real world MAXCUT.
Raw
Onehot
RandFeat
DAD
Optsicom-B
1.14e
3.49e 5
9,92e
4.23e
Optsicom-G
1.15e
8.79e
2.93e
1.16e
Here include more ablation results, on both real world datasets (see Table 7 and Table 6) and synthetic datasets (see figure 12). We can see the conclusion is still consistent with our claim in the main paper.
16

---

Under review as a conference paper at ICLR 2021
1023
1.3
1.06
Gunge)
1.020
D42 precdly
DAO
1.0
DAD 2e0-r
Ratio wattowtt Gumbi
1.05
2.04
DAC pread)
1.015
DAG tree2
DRC bunce
1.06
Raw
BAD trased
RaN
1.04
1.02
1.005
1.01
1.000
64.75
256
1.00
16.20
32-10
66-75
128-150 256-100
1.00
16-20
32-40
64-75
120-150 255-100
# nodes travitess grapro
nodes Intrain graphe
4 nodes tralitestt graphs
MVC-ER Supervised
MDS-ER Supervised
MaxCut-ER Supervised
1.10
1.82
1.56
DAD
DAD graggyddyy
DAD
bep-gmety
1.0175
1.0200
DA2
BAC grandy
1.0025
1.0030
0
1.0125
DAG breet
1.0015
RUy
1.33
100775
RoN
1.02
1.0050
1.0005
1.01
1.0000
16-20
12-40
64:15
126-150
256-300
1.00
16.20
32.40
64-75
128-150
256-201
1.0000
16:20
66-75
128-150 256-300
nodes
nitest grapts
nodes in train'iast grapts
nodes trainttest grashs
MVC-BA Supervised
MDS-BA Supervised
MaxCut-BA Supervised
E43
BAD
1.14
DAC:
EAD
5380 Guroat
1.05
D62
3.25
D&O groedy
BAD
Reto wrr Gunni
3.10
1.12
D&D groccly
DXC-treesd
1.04
1.20
3.08
1.03
3.06
1.04
1.1
1.05
1.02
1.00
1.00
1.00
32:45
54-75
200-300
rodes tralittet
modes traindess graphs
modes tmal-best
MVC-ER Unsupervised
MDS-ER Unsupervised
MaxCut-ER Unsupervised
1.000
1.025
DAD-grasyy
BAP
240 Urenz
1.14
BAG
BAC I.C-treed
D&2 gko-groodyy
Satto W.7A
3.08
BAD treec
BAD gredddyyyy
Aak
D60 urocel
3.020
D&O trenzz
2.06
2.04
1.000
1.005
1.02
16-25
32:40
64-75
128-150
256-300
32-40
54-75
255-300
tranttes grapns
graphs
graphs
MVC-BA Unsupervised
MDS-BA Unsupervised
MaxCul-BA Unsupervised
Figure 12: Ablation studies on synthetic graphs. ER stands for Erdos Renyi random graphs, and BA stands for Barabasi Albert graphs.
F.3.1 ABLATION ON FEATURE DIMENSION
As our algorithmic feature augmented GNNs have more dimensions in the node and edge features, the input layer thus has more parameters than some of the baseline features. For more rigorous comparison, we have padded the baseline features to the same dimension, and thus all the methods would have same neural network capacity.
Specifically, for the Raw baseline, simply pad constant 1 (or edge weights, when applicable) to the same dimension as DAD. For RandFeat baseline, we augment additional random features to match the dimensionality. The two variants are denoted as
and HandFeat-Multe
Figure 13 shows the results across three tasks, with either supervised or unsupervised setting, on two types of random graphs. We can see for some cases the RandFeat -Multi would improve bit over RandFeat, but overall the -Multi variant is comparable as its original counterpart, while being worse than DAD in all cases. This confirms that DAD's s gain of performance is not mainly coming from larger networks, but indeed the algorithmic features improve the global information representation quality.
17

---

Under review as a conference paper at ICLR 2021
182
1.3
1.06
RAD
1,020
D4D
Naw
110
S/B
Ratio wittowot Gumbi
1.05
2.04
KandFear
Sze
1.015
Rardfest
Randfesimuli
Bardfesh-mutt
1.06
1.04
1.02
1.005
1.01
1.000
65.75
1.00
18-20
66-75
128-150
256-100
1.00
16.20
12-10
64-25
128-150 236-300
nodes in wratrroiiect VicS: grapho
nodes Intrainn
4 nodes traliitest graphs
MVC-ER Supervised
MDS-ER Supervised
Maxcut-El ER Supervised
D4.3
BAD
1.14
BMD
Handheol
1.05
1.06
Ran
Bandfeak
Ri
1.25
1.30
Ran
Bandfeet
Rea-met
Patlo 1.mh
3.10
1.12
Raw
kow madt
RandFeak
Ratlo
1.04
1.08
1.06
1.02
2.04
1.41
1.05
1.00
1.00
1.00
modes
nodes tralntest
nodes
MVC-ER Unsupervised
MDS-ER Unsupervised
Maxcut-ER Unsupervised
1.52
107
110
1.26
1.0055
10220
1.0030
Bwemd:
Tue-mul
Tund"au
1.0150
Kow-mall
1.000
1.0125
1.0015
1.0075
1.0030
1.01
10022
100000
1.00
rodes tratttaleest
hodes tralntess
MVC-BA Supervised
MDS-BA Supervised
Maxcut-BA Supervised
1.000
1.025
Faw
DAD
Rasshon Randfasttmmat
BAG
Rsn-mut
Safto W.TAG
3.08
Saw muhh
Nue
Rancheal-m.li
RandFeat
3.020
1:10
Bandfeatrmah
Randteal
3.06
1.000
1.005
1.02
16.20
32:45
64-75
128-159
250-300
16-20
128-150 graphs
22-40
graphs
graphs
MVC-BA Unsupervised
MDS-BA Unsupervised
Maxcut-BA Unsupervised
Figure 13: Test approximation ratio by padding baseline features into same dimension.
F.3.2 MORE TIME-SOLUTION TRADE-OFF PLOTS
We here include the time-solution trade-off plots for all tasks on 2 types of graphs. We vary the average size of graphs in {256, 512, 1024]. All the evaluation is done using 16 threads, where the baselines are run using embarrassingly parallel setup (i.e., the average runtime is divided by 16), DAD consistently
and DAD runs 16 CPU + GPU mixed parallelism. From Figure 14, achieves good trade-off between the time and solution quality.
G COMPARISON WITH GNNEXPLAINER
In this section, we compare the explanation quality against the GNNExplainer. Without loss of generality, we carry out the explanation experiments the GNN that is supervised trained for BA graphs with 32-40 nodes, for MVC task.
For GNNExplainer, regularizer coefficient to be 1, and tune the coefficient for the sparsity regularizer in {0.1, 1.0, 10.0). We learn the node and edge masks using Adam optimizer, for at most 3000 gradient update steps.
follow the implementation from pytorch geometric. We the entropy
18

---

Under review as a conference paper at ICLR 2021
We visualize the explanation provided by DAD and different configurations of GNNExplainer in Figure 15. In the figure, the node with red boundary color is the target node to be explained. For blue color to indicate the selected nodes un-selected ones. We fix the explanation budget to be 5 nodes and 10 edges for DAD. For GNNEx- plainer, the darkness of the color indicates the score of the soft selection.
DAD,
edges, and gray color indicate the
We can see all the explainers can at least select the target node as the important node when explaining the target node. This least shows that the explainers doing reasonable jobs. We can also from the figure that, DAD can offer some node degree-based explanations for the first and second rows, while GNNExplainer failed to so, as it either has only one edge with outstanding score, or has a hard time balancing the number of edges with the explanation fitmess. Also, from the last row, we can see DAD is able select some disconnected anchor nodes (see section 5.4) for explanation while GNNExplainer needs either too large too small chunk of connected subgraphs.
19

---

Under review as a conference paper at ICLR 2021
Aperox Ratoo
logi-tppex oeporce drvedy
2.4
3:29
DMO Liii
Approx 101
DAB Oreelt
3.3
LP fotse
Approx
Gurnal
Gardb
2.3
11
32'
12
Time (ms)
Time (ms)
Time (ms)
MVC-Barabasi Albert- 1024 1024
MDS- BoS-BBaabasii Albert-1000
Albert- 1024
2.4
DADU Greedy
BAb
Approx Ratio
Logli-iporce
Gready
ZApa to wrddy
Mastrahall
2.22
2.81
Time (ms)
Time (ms)
Time (ms)
MVC-Erdos Renyi-1024
MDS-Erdos Renyi-1024
Maxcut-Erdos Renyi- Renyi-1024
125
Approx Rattoo
3.4
Expu
Approx Ratio
A20
Gready
Gready
Approx
1.2
3.91
(ms)
(ms)
MVC-Barabasi Albert-512
SDDS-Barabasi Albert-512
Maxcut-Barabas Albert-512
Approx Ratio
2.5
DAD-J
Logl-Appres
CAC-y
Cready
2.84
Rhoante
3.4
2.82
39
33
35
3P
12
10
10
Time (ms)
Time (ms)
Time (ms)
MVC-Erdos Renyi-512
MDS-Erdos Renyi-512
Maxcut-Erdos Renyi-512
Approx Rabo
35
Logg Sapera
Zegpors diveedy
Approx Ratio
3.00
1.20
DWD LPaES
DADU
Creedy
3.2
Approx
Sie
Curde
215
3.2
39
Time (ms)
Time (ms)
T Time (ms)
MVC-Barabasi Albert-256
MDS- Barabasi Albert-255
Maxcut-Barabasi Albert-255
338
Approx Ratio
332
Lechi-eerre Mlop Geeedy
2.
Seedy
3.88
Approx
Sardi
3.95
Oueesi
3.3
045
Time (ms)
(ms)
Time (ms)
MVC-Erdos Renyi-256
MDS-Erdo Renyi-256
Maxcut-Erdos Renyi-256
Figure 14: Time and approximation ratio trade-off plot for different methods.
20

---

Under review as a conference paper at ICLR 2021
DAD
GNN-EXP-0.1
GNN-EXP-1
GNN-EXP-10
Figure 15: Comparing explanation results with GNNExplainer using different sparsity regularization coefficients.
21


Reviews:
[{"review_id": "mhgXH9UbPgo", "reviewer": "AnonReviewer3", "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": "In this paper, the authors proposed a framework for differentiable graph algorithm discovery (DAD). The framework is developed by improving two the discovery processes, i.e., designing a larger search space, and an effective explainer model. To enlarge the search space, the proposed DAD augments GNNs with cheap global graph features, which consist of solutions on the spanning trees of the original graph, and approximate solutions of greedy algorithms. All the features are concatenated together as input to GNNs. Experiments indicate that the proposed DAD is better than the approximate solutions. The explainer model is developed to explain the learned GNN, by employing the learning to explain (L2X) framework in (Chen et al., 2018). In general, the paper is well-written, and the method is interesting.\n\nSome questions and comments:\n\n1.  Although the authors have provided an ablation study to verify the contributions of tree solution versus greedy solution in Figure 11 in appendix, it is still not very clear about the impact of the global features on the model. The ablation study is short and lacks detailed discussions. In Figure 11, what is \"raw\" model? The global features are concatenated to the input, which actually increases the dimension of features. It would be necessary to see whether the global information or the extra degrees of freedom improve the performance.  \n\n2. How to determine how many spanning tree solutions or greedy solutions is enough for performance improvement? The authors said that \"We tuned the hyperparameters of GNN models for each graph category, such as the number of layers and the number of spanning trees, using grid search. \" It sounds like the proposed model is hard to generalize to different datasets.\n\n3. The novelty of the explainer model is not very clear. It seems that the authors just applied the learning to explain (L2X) framework in (Chen et al., 2018) to the GNN settings.\n\n4. There many typos, e.g., \n(1) In page 4, \"treat the l constraints seperately for efficient computations\",    --->  separately \n(2) In page 5, above Eq.(11), \"is irrelavent to nodes of distrance larger than T\"   --> irrelevant, distance\n(3) In page 5, \"is defined to be the origianl GNN\"   --> original\n(4) In page 6, \"add a global read-out functionto\"   --> function\n\n\nI have read the authors' response, and I would like to keep my current rating.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "klQAnPwonZ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Summary:\nThis paper proposes a framework to discover graph-algorithms that are learned by neural networks to solve combinatorial optimization problems. To this end, the authors propose (a) augmenting the input of DNN-solver using features extracted by existing combinatorial algorithms and (b) explaining the DNN based on an additional \"explainer\" model trained based on maximizing the lower bound of mutual information between subgraph of the input and the labels predicted by the DNN solver. I think this paper pursues an important and promising direction to extract algorithms from DNN-based solvers. However, I think (a) additional baselines should be incorporated for evaluating the DNN-solver, (b) the proposed explainer does not generate practically useful outputs for discovering new algorithms, and (c) the proposed explainer seems a bit flawed.\n\nStrength:\n- The proposed augmentation scheme gives interesting insights and can be applied to other DNN-based solvers for combinatorial optimization.\n- This paper tackles an interesting problem of discovering new algorithms from DNN-based solvers for combinatorial optimization.\n\nWeakness:\n- It is not clear why the authors only consider baselines with polynomial-time running time. To show that the proposed DNN-based solver is practically useful, the authors should compare with state-of-the-art solvers (both DNN-based and non-DNN-based) under limited running time. To compare the algorithms based on the tradeoff between complexity and approximation ratio, the authors should provide a theoretical analysis of the approximation ratio of the proposed algorithm.\n- It is not clear how to use the proposed algorithm for discovering new graph algorithms. Especially, the algorithms produce results that are not very \"explainable.\" For example, how did the authors use the explainer to \"re-discover the node-degree greedy algorithm?\" The proposed framework seems to assume that humans can easily analyze the provided explanations (i.e., graphs with colored nodes). However, it seems hard for me to analyze the pattern in node-degree of nodes just by glancing at several explanations provided by the proposed framework. Such a process becomes especially harder if we aim to discover algorithms based on novel concepts (instead of node-degree). Even more, researchers are usually interested in developing algorithms for large-scale graphs (where exact solutions are intractable), yet the explanation becomes notoriously hard to analyze in the eyes of humans for this case. The authors are encouraged to provide an actual process of extracting analysis on the explanations, e.g., did they (1) look at hundreds of explanations provided by the explainer, (2) intuitively group explanations with the common pattern in node-degree, and (3) infer a greedy pattern in node-degree of the selected nodes?\n- The proposed explainer seems flawed for explaining the DNN-based solver. Namely, the proposed explainer only accesses the DNN-based solver based on its prediction probability. However, I do not think it makes sense to rely only on the prediction to explain the black-box algorithm. To demonstrate, both the brute force search and integer programming solver will give an identical prediction (i.e., optimal solution) for the combinatorial optimization. Applying the proposed explainer to two algorithms would give an identical explanation, but brute force search and integer programming operate in a very different way. \n\n---\n\nI appreciate the thoughtful rebuttal provided by the authors. My main concerns are on Q2, i.e., the practical usefulness of the algorithm. I do think that the authors provide a convincing argument on \"we can only understand what we can understand,\" hence we should set up a hypothesis and see if it aligns with the explanation. However, I think the usefulness is not well-supported in the current state of the paper. The authors can come up with (a) a stronger example of such a hypothesis and (b) a better measurement of how the hypothesis aligns with the explanation to strengthen the paper. \n\nRegarding Q3, I still think that it is not correct to provide the same explanation for different algorithms when they produce the same output. Hence, the proposed algorithm should be modified to consider this aspect. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eWHLT_C0EYS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 paper has provided an explainable GNN framework using differentiable graph discovery algorithm. To me more specific, it utilize the solution over spanning trees greedy approximation and the explainer GNN is able to provide the influential node/edges. The experimental results has demonstrated the effectiveness of the proposed framework.\n\n The idea of the model is quite neat and artful designed and it is also intuitive formulate as ILP problem. However, I do have some concerns as follows:\n\n1) In terms of the explainable GNN, I doubt the presenting systematic explanation of the graph model is explainable. It lacks of the details of perspective of explainability/interpretability definition over in either quantitative manner or qualitative way(e.g. user study/case study in downstream task). It could be still regarded as an open problem in AI transparency and I'm not criticizing this paper has not provided the corresponding merits. However, explaining the graph models leveraging as node/edge selections probably not uniform solution but a neat idea.\n\n2) The paper also mentions the work provided by GNNExplainer, it would be more confident to believe your proposed method is optimal if considering the GNNExplainer as baseline. More importantly, it would be essential to reason why your proposed framework is better in terms of explainability.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for automatically discovering graph algorithms using GNNs. In general, the reviewers find the paper well-written, and the problem and the approach interesting.  However, there is a concern on the practical usefulness of proposed method as shown in the following comments:  “My main concerns are on Q2, i.e., the practical usefulness of the algorithm”[R1]; “It sounds like the proposed model is hard to generalize to different datasets” [R3]; “The proposed explainer does not generate practically useful outputs for discovering new algorithms”[R4]. 
Decision: Reject