Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The term "structural equivalence" is used incorrectly in the paper.  From sociology, two nodes with the same position are in an equivalence relation.  An equivalence, Q, is any relation that satisfies these three conditions:
  - Transitivity: (a,b), (b,c) ∈ Q ⇒ (a,c) ∈Q
  - Symmetry: (a, b) ∈ Q if and only if (b, a) ∈Q
  - Reflexivity: (a, a) ∈Q

There are three deterministic equivalences: structural, automorphic, and regular.

From Lorrain & White (1971), two nodes u and v are structurally equivalent if they have the same relationships to all other nodes.  Exact structural equivalence is rare in real-world networks.

From Borgatti, et al. (1992) and Sparrow (1993), two nodes u and v are automorphically equivalent if all the nodes can be relabeled to form an isomorphic graph with the labels of u and v interchanged.

From Everett & Borgatti (1992), two nodes u and v are regularly equivalent if they are equally related to equivalent others.

Parts of this statement are false: "A notable example of such approaches is RolX (Henderson et al., 2012), which aims to recover a soft-clustering of nodes into a predetermined number of K distinct roles using recursive feature extraction (Henderson et al., 2011)."  RolX (as described in KDD 2012 paper) uses MDL to automatically determine the number of roles.

As indicated above, this statement is also false: "We note that RolX requires the number of desired structural classes as input, ...".

The paper does not discuss how the free parameter d (which represents the number of evenly spaced sample points)  is chosen. 

This statement is misleading: "In particular, a small perturbation of the graph yields small perturbations of the eigenvalues."  What is considered a small perturbation?  One can delete an edge (seemingly a small perturbation) and change the eigenvalues of the Laplacian dramatically --  e.g., deleting an edge that increases the number of connected components.

The barbell graph experiment seemed contrived.  Why would one except such a graph to have 8 classes?  Why not 3?  One for cliques, one for the chain, and one for connectors of the clique to the chain.

In Section 4.2, how many roles were selected for RolX?

The paper states: "Furthermore, nodes from different graphs can be embedded into the same space and their structural roles can be compared across different graphs."  Experiments were not conducted to see how the competing approaches such as RolX compare with GraphWave on transfer learning tasks.

Gilpin et al (KDD 2013) extended RolX to incorporate sparsity and diversity constraints on the role space and showed that their approach is superior to RolX on measuring distances.  This is applicable to experiments in Figure 4.

I strongly recommend running experiments that test the predictive power of the roles found by GraphWave.

review_title: This paper uses spectral graph wavelet diffusion patterns of a node’s local neighborhood to embed the node in a low-dimensional space.  In this low-dimensional space, nodes with similar local neighborhoods are close to each other even if they are far in graph distance.  The methodology of the paper is fine but the experiments section is weak and the paper misses clear connections to sociology.

final_score: rating: 3: Clear rejection
review_content: The paper proposes a method for quantifying the similarity between the local neighborhoods of nodes in a graph/network.

There are many ways in which such a distance/similarity metric between nodes could be defined. For example, once could look at the induced subgraph G_i formed by the k-neighborhood of node i, and the induced subgraph G_j of the k-neighborhood of node j, and define the similarity as k(G_i,G_j) where k is any established graph kernel. Moreover, the task is unsupervised, which makes it hard to compare the performance of different methods. Most of the experiments in the paper seem a bit contrived.

Regarding the algorithm, the question is: “sure, but why this way?”. The authors take the heat kernel matrix on the graph, treat each column as a probability distribution, compute its characteristic function, and define a distance between characteristics functions. This seems pretty arbitrary and heuristic. I also find it confusing that they refer to the heat kernel as wavelets. The spectral graph wavelets of Hammond et al is a beautiful construction, but, as far as I remember, it is explicitly emphasized that the wavelet generating function g must be continuous and satisfy g(0)=0. By setting g(\lambda)=e^{-s \lambda}, the authors just recover the diffusion/heat kernel of the graph. That’s not a wavelet. Why call this a “spectral graph wavelet” approach then? The heat kernel is much simpler. I find this misleading.

I also feel that the mathematical results in the paper have little depth. Diffusion is an inherently local process. It is natural then that the diffusion matrix can be approximated by a polynomial in the Laplacian (in fact, it is sufficient to look at the power series of the matrix exponential). It is not surprising that the diffusion function captures some local properties of the graph (there are papers by Reid Andersen/ Fan Chung/ Kevin Lang, as well as by Mahoney, I believe on localized PCA in graphs following similar ideas). Again, there are many ways that this could be done. The particular way it is done in the paper is heuristic and not supported by either math or strong experiments.

review_title: The method is ad-hoc, there is no genuine experimental baseline, the mathematical derivations make the paper look more sophisticated but do not provide actual insight.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper derived a way to compare nodes in graph based on wavelet analysis of graph laplacian. The method is correct but it is not clear whether the method can match the performance of state-of-the-art methods such as graph convolution neural network of Duvenaud  et al. and Structure2Vec of Dai et al. in large scale datasets.  
1. Convolutional Networks on Graphs for Learning Molecular Fingerprints. D Duvenaud et al., NIPS 2015. 
2. Discriminative embeddings of latent variable models for structured data. Dai et al. ICML 2016.


review_title: The method is based on a principled derivation, but have not compared with other state-of-the-art

Meta-review: The reviewers present strong concerns about the lack of novelty in the paper. Further there are strong concerns about how the experiments are conducted. I recommend the authors to carefully go through the reviews.
Decision: Reject