We will use the well known Performance Difference Lemma [16] in our analysis. We can obtain a performance difference lemma for the meta-policies as follows. Here, we get (a)is from Assumption 3.1 from which we have P In this section, we describe all the simulation and real-world environments in detail. B.1 Simulation Environments Point 2DNavigation: Point 2DNavigation [9] is a 2 dimensional goal reaching environment with S R2, A R2, and the following dynamics, xt+1 = xt +dxt, yt+1 = xt +dyt, such that dx2t +dy2t 0.12 Where xt and yt are the x and y location of the agent, dxt and dyt are the actions taken which correspond to the displacement in the x and y direction respectively, all taken at time step t. The goals are located on a semi circle of radius 2, and the episode terminates when the agent reaches the goal or spends more than 100time steps in the environment.

Recently, graph neural networks [42, 87] emerged as the most prominent (supervised) GRL architectures. Notable instances of this architecture include, e.g., [31, 47, 97], and the spectral approaches proposed in, e.g., [19, 30, 56, 72]--all of which descend from early work in [57, 69, 87, 90]. Recent extensions and improvements to the GNN framework include approaches to incorporate different local structures (around subgraphs), e.g., [2, 36, 50, 82, 106], novel techniques for pooling vertex representations in order perform graph classification, e.g., [20, 37, 108, 113], incorporating distance information [110], and non-euclidian geometry approaches [22]. Moreover, recently empirical studies on neighborhood aggregation functions for continuous vertex features [28], edge-based GNNs leveraging physical knowledge [4, 58], and sparsification methods [85] emerged. A survey of recent advancements in GNN techniques can be found, e.g., in [21, 103, 114]. Dasoulas et al. [29], Abboud et al. [1] investigate the connection between random coloring and universality. Recent works have extended GNNs' expressive power by encoding vertex identifiers [80, 98], adding random features [86], using higher-order topology as features [18], considering simplicial complexes [3, 14], encoding ego-networks [109], and encoding distance information [61]. Although these works increase the expressiveness of GNNs, their generalization abilities are understood to a lesser extent. Further, works such as Vignac et al. [98, Lemma 6] and the most recent Beaini et al. [11] and Bodnar et al. [14] prove the boost in expressiveness with a single pair of graphs, giving no insights into the extent of their expressive power or their generalization abilities. For clarity, throughout this work, we use the term GNNs to denote the class of message-passing architectures limited by the 1-WL algorithm, where the class of distinguishable graphs is well understood [5].

Graph neural networks (GNNs) have limited expressive power, failing to represent many graph classes correctly. While more expressive graph representation learning (GRL) alternatives can distinguish some of these classes, they are significantly harder to implement, may not scale well, and have not been shown to outperform well-tuned GNNs in real-world tasks. Thus, devising simple, scalable, and expressive GRL architectures that also achieve real-world improvements remains an open challenge.

Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current scope of neural solvers for NPC problems by introducing a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete {0,1}-vector optimization problems and leverages graph-based denoising diffusion models to generate high-quality solutions. We investigate two types of diffusion models with Gaussian and Bernoulli noise, respectively, and devise an effective inference schedule to enhance the solution quality. We evaluate our methods on two well-studied NPC combinatorial optimization problems: Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Experimental results show that DIFUSCO strongly outperforms the previous state-of-the-art neural solvers, improving the performance gap between ground-truth and neural solvers from 1.76% to 0.46% on TSP-500, from 2.46% to 1.17% on TSP-1000, and from 3.19% to 2.58% on TSP-10000. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.

For PCA-based methods, the dimensionality reduction is performed via singular value decomposition (SVD) of the input one-hot encoding matrix X. As mentioned above, we utilize grid search for tuning the hyper-parameters. In particular, for the learning-based methods, including GraphSAGE and KS-GNN, the learning rates are selected from {0.1, 0.01, 0.001, 0.0001}. GraphSAGE, SAT, Conv-PCA, KS-PCA, KS-GNN), we swept the number of hidden layers in the set {1, 2, 3, 4, 5}. For the other hyper-parameters used in KS-GNN, such as λ1, λ2 and λ3, we tune them from 0.1 to 1 with a step of 0.1.

Keyword search is a fundamental task to retrieve information that is the most relevant to the query keywords. Keyword search over graphs aims to find subtrees or subgraphs containing all query keywords ranked according to some criteria. Existing studies all assume that the graphs have complete information. However, real-world graphs may contain some missing information (such as edges or keywords), thus making the problem much more challenging. To solve the problem of keyword search over incomplete graphs, we propose a novel model named KS-GNN based on the graph neural network and the auto-encoder. By considering the latent relationships and the frequency of different keywords, the proposed KS-GNN aims to alleviate the effect of missing information and is able to learn low-dimensional representative node embeddings that preserve both graph structure and keyword features. Our model can effectively answer keyword search queries with linear time complexity over incomplete graphs. The experiments on four real-world datasets show that our model consistently achieves better performance than state-of-the-art baseline methods in graphs having missing information.