Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes the use of topological features into the graphs for the task of node classification. The proposed approach uses two modules for this purpose, the Topologically Induced Multigraph Representation module (TIMR) and the STAN (Subgraphs, Topology and Neighbour attribute) module. The TIMR module builds topological features from the k-hop neighbourhood of the graph. It finds the persistence diagrams (0 dimensional) of the k-hop neighborhood of every node. The filtration takes place depending on the node degree or the edge weights (computed by the distance between the node attributes). Once the persistence diagrams (PDs) for the nodes are found the pairwise Wasserstein distance is computed for these PDs. If it is less than a threshold (\epsilon1) a positive edge (+1) is added to the adjacency matrix and if it is greater than another threshold (\epsilon2) a negative edge (-1) is added. In the final adjacency matrix W^{topo} is defined as 1 if the combined sum in the previous step is greater than 0, else 0. This matrix is then used to find a modified Laplacian which is used in the GNN layer to aggregate node features from the STAN module. The STAN module is used to learn node features from the topology and node attributes. The edge weights are computed by normalizing over the Wasserstein distances in the neighbourhood of the node which is used in the weighted averaging followed by the aggregation layer that combines the neighbourhood information with the node’s features. The topology induced adjacency matrix (obtained from TIMR) and the node features (from the STAN module) are fed to the TRI-GNN layer with the proposed modified Laplacian and this module learns the parameters for performing the task of node classification. The proposed method performs well in comparison to the baselines.
main_review: -- Strengths:	
1. Induces topological information from the node neighborhood by adding/deleting edges that are topologically similar/dissimilar

2. Learns node features from the edges weighted by the topological distance, thus introducing an attention over the neighbourhood based on topology

3. The proposed method performs well in comparison to the baselines

-- Weaknesses:	
1. The paper states that the method uses 0 cycles for computing the PDs. These 0-dimensional PDs just contain connectivity information in terms of the number of connected components, which can easily be deduced with other graph-theoretic algorithms. Is there a reason why authors do not use any higher-dimensional PDs? Also the paper states in section 4.1 regarding the aim “Our aim is to systematically extract all k-dimensional topological features and their persistence in each node neighborhood and then to compare node neighborhoods in terms of their exhibited shapes“. However this doesn’t seem to be backed up empirically.

2. A thorough time-complexity analysis would have been more useful. The overall time-complexity of the method seems quite large considering that PDs have to be computed per node in addition to pairwise Wasserstein distances. It looks like the method would not scale well to large (or massive) graphs. Please address this point in the rebuttal.

3. The added topological information has not been learned end-to-end in a differentiable manner thus preventing any adaptive learning. For example, if the existence of a homology class in the neighbourhood of a node would result in that node belonging to a certain class. Ideally this structure should be detected and used for prediction. However this would not be possible by simply using the hardcoded topological features. 

4. This work seems to leverage homophily as an inductive bias. I am not sure why edges must be removed between nodes whose neighborhood topology differs? This idea might not work so well for graphs which exhibit a lot of heterogeneity. For example, a graph with bank customers as nodes and some transaction history dictating edges (and their weights) between customers, can easily have forgers or attackers as nodes in the graph, that are surrounded with customer nodes (that are very different from the attacker). Such a situation is quite realistic in real-life. 

5. The graphs picked for the experiments might be exhibiting a high degree of homophily among nodes. It would be interesting to see how this method performs on non-homophilous datasets. Such datasets can be found in:
“New Benchmarks for Learning on Non-Homophilous Graphs” - Lim et. al (WWW’21).

6. In Theorem 1, K(eps1,eps2) is a function dependent on eps1 and eps2. I am not sure how this bound is of any use because K(eps1,eps2) could be arbitrarily large or even unbounded depending on the choice of eps1 and eps2. It would be more useful to present a study about how these bounds behave in different regimes and choices of parameters eps1 and eps2. How are eps1 and eps2 determined? This is not discussed in the paper.

7. In definition 4.1, how is the “k” in the k-hop neighborhood determined? How does it work in the case of sparse vs. dense graphs? Or graphs with low average degrees vs. those with high-average degrees? 

8. It would be more interesting to use graph adversarial attacks in the experiments that just don't perturb random edges/nodes etc. but do something smarter. E.g. 
"Towards More Practical Adversarial Attacks on Graph Neural Networks" - Ma. et. al. (NeurIPS 20).

limitations_and_societal_impact: There was no societal impact section in this paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The work proposes an extension to conventional graph neural networks by
incorporating additional information about local topological structures in the
proximities of nodes.  The core contribution of the work is to additionally
allow rewiring of the graph based on the similarities of topological structures
of pairs of nodes.  It is shown that these rewirings can lead to increased
robustness of models against graph perturbations or adversarial attacks.  The
model is evaluated on a series of Node Classification tasks and is shown to
have favorable performance compared to many baselines.

main_review: The work is well written and motivated and the paper is well structured.
Experiments are detailed and ablations are preformed to show the contribution
of individual model components (where some improvements could be made, see
major comment 1).  I have some concerns with regard to reproducability of the
results as hyperparameters are not exactly documented, further I am unable to
verify the selection process of hyperparameters (major comment 2).

Generally, the approach is novel and can represent a promising direction for
integrating aspects from topological data analysis into a Graph Neural
Networks.  

Major comments:
 1. Removing individual components of the model can significantly impact the
    expressiveness of a model.  I would recommend to instead of removing the
    components, to implement fake versions which do not actually rely on PH.
    In the case of the TIMR ablation one could for example use random features
    as the basis of distance computations between nodes.  Without such
    ablations it is hard to tell if the reduced performance is due to lower
    model expressivity or due to the removal of the component.
 2. The search of hyperparameters seems to be largely limited to the presented
    method, which can give the approach a competitive advantage.  Further, the
    exact procedure for deriving the hyperparameters is not entirely clear.
    Which metric was used for deriving the best hyperparametes? Which ranges
    were evaluated?  Was the metric computed on a held out validation set or via
    cross validation?  What are the exact hyperparameters used for each model?
    The details are crucial to asses the study design and to estimate how
    representative the performance of the model is and pinpoint potential
    biases.

Minor comments:
 1. The graph corruption experiment could be extended to also incorporate
    corruption of node features.  While this is not covered by the stability
    theorem, it would still be interesting to see how the models perform based
    on different perturbations of the input.

limitations_and_societal_impact: The authors have not addressed the social impact of their work.  While I think
that the implications are of limited degree, there are some potential
directions that could be mentioned here.  In particular, graph algorithms for
node classification can be used to categorize people using observational data
and include how they interact with others.  While this can
mostly be used for the good of developing better products or offering targeted
advertisement, it could also be used in surveillance systems where the social
implication would be non-negligible.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: To tackle the over-smoothing problem in GNNs, this work proposes to use topological relational inference for systematically learning local graph structures. The similarity between two local graphs are measured by the persistent homology. A “multiedge” is added between two nodes whose local graphs are similar enough.  The local topological side information is added enrich the features of each node. Theoretical stability guarantees were derived for the above new graph representation. The experimental results provide empirical evidence to support the proposed approach.
main_review: Originality: The idea of using persistent homology to define neighborhood similarity between nodes is relatively novel. It may be a new direction for better understanding the graph algebraic connectivity.

Significance: A nice attempt to better utilize local topological information. Derive theoretical stability guarantees for the new local topological representation of graph.

Quality: I have several concerns. The way of constructing the ‘joint topology-induced adjacency matrix’ needs further consideration. The topology-induced adjacency matrix somehow tangles the connection information and the topological side information (eq. (3) in Section 4.4). STAN uses traditional neighborhood aggregations except for a different measurement in node distance, which make it limited. Although the proposed approach outperforms some baseline models on the Cora, CiteSeer, and PubMed datasets, it remains limited compared to other GNN models (e.g., NodeNet and GCN-label propagation). For example, NodeNet achieves around 86% accuracy on node classification tasks on Cora.

Clarity: The first several sections of this paper are OK. The model, implementations, and experiment sections need improvements. The explanations about TDA can be improved. As it is written now, it is hard for readers to understand the idea without enough background knowledge. There are several places that need some clarifications. For example, how sequence {Gi} induces the filtration of complex {Ci}, how to decide the value of k, the similarity between graph {Gi} and {Gi+1}, and so on. How to deal with continuous attributes in the attribute-based filtration of persistent homology? 

limitations_and_societal_impact: No potential negative societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a way of rewiring an input graph using persistent homology and propose a class of GNNs that operate on top of this rewiring. The authors discuss and analyse the implications of such an approach for adversarial robustness, stability to graph perturbations and improving node classification performance. 
main_review: ## Strong points

- To the best of my knowledge, graph rewiring via persistent homology (PH) is a new and original idea. So far, applications of persistent homology in geometric deep learning have focused primarily on graph classification, with the notable exception of the paper *Persistence Enhanced Graph Neural Network*, which the authors also comment on. 
- I appreciate that the authors attempted to provide some theoretical stability guarantees about their proposed rewiring scheme. While PH has been used extensively in the field, its theoretical properties are rarely extended to the newly proposed methods. Therefore, this is an appreciable effort. At the same time, I have certain questions/doubts about the proof (see below). 
- I appreciate the authors have added an ablation study, which clearly identifies the source of the improvements. 
- The experiments have been run over a significant number of seeds (50), use a significant number of baselines, and the statistical significance is often explicitly stated. 
- The robustness analysis nicely complements the theoretical results on stability to perturbations. 
- Figure 1 does a good job of illustrating how the different pieces are coming together. 

## Improvements

- I believe the main limitation of the work is that the experimental evaluation focuses only on a set of datasets with very small graphs. While these datasets could also provide valuable information about a method, it only shows how a method performs in a very limited setting. The limitations of these datasets have been widely studied recently (e.g. https://arxiv.org/abs/2003.00982). Therefore, I wished the authors complemented these experiments with (some) benchmarks from OGB (https://ogb.stanford.edu/) or the Benchmarking GNNs paper (https://arxiv.org/abs/2003.00982). These limitations also transfer over to the perturbation stability experiments. 
- The presentation of the paper can be improved from many points of view:
  - The introduction to persistent homology is probably too abrupt for the average reader, who is likely not familiarised with persistent homology. For instance, the authors mention a simplicial complex when introducing PH, but simplicial complexes are never defined. Furthermore, I believe they are not even needed since this work is only interested in graphs (i.e. 1-dimensional simplicial complexes). At the same time, the authors mention k-dimensional topological features. But again, since we are talking about graphs we are not interested in k > 1. So these terms can be completely excluded to avoid confusing people and maintain only a minimally required technical jargon. A recent brief introduction to PH that I liked can be found in the background section of https://arxiv.org/abs/2102.07835. Notice how the authors use various examples to build an intuition. Perhaps the authors could borrow some ideas from there in the way the background material can be presented. 
  - On the latter point, many definitions lack an intuitive explanation or justification. For instance, the intuition behind the Wasserstein distance is never explained. Or the intuition/motivation behind the expression for $W_{uv}^{topo}$ below line 264, which otherwise might seem a bit arbitrary. 
  - While the Figures offer a pretty good visual description the captions are too brief and offer little information. For instance, the size of the arrows in Figure 2 and the colours of different elements are not explained at all.
  -  The paper is overflown with acronyms (TIMR, STAN, TRI-GNN) and the authors do not explain very well how all these pieces are coming together. I've understood this only after noticing in Figure 1. However, the main text never provides a unifying view and the sections seem a bit disconnected because of this. The order they are presented in could also be improved. I was very confused by how STAN and TRI-GNN interact since both of them produce multiple layers of features. This is roughly clear from the Figure, but still, I feel like I am missing many details. 
 - I do not think it was explained (apologies if I missed it), but how are the results for the baselines produced? Are they taken from other papers or have the authors trained them? If it is the latter, how where these baselines fine-tuned to ensure a fair comparison. 
- I am confused by lines 12-15 of the proof, which seem very hand-wavy to me. Could you explain more rigorously what is going on in those lines? I would have expected to see a series of inequalities leading to the desired inequality but this flow is quickly interrupted in line 12 where everything is just stated in words and the logical argument becomes very ambiguous. 
- I believe the computational complexity of the method was not stated. 
- Nit: Another topological approach for higher-order interactions which is not cited was introduced in https://arxiv.org/abs/2103.03212. 

EDIT: After discussion, I decided to raise my score from 6 to 7. 
limitations_and_societal_impact: The authors have not included a section on limitations and societal impact.
review_title: null

Meta-review: While the paper initially obtained quite mixed reviews and some reviewers flagged ethical concerns, a substantial amount of constructive discussion among the authors and the expert reviewers (both technical and ethical) eventually clarified many issues. Taking into account all changes and clarifications mentioned (and promised) by the authors, the revised manuscript will be a valuable contribution to the field. I do, however, encourage the authors to take all comments seriously and adjust the manuscript accordingly (especially regarding notation, presentation, choice of hyperparameters, social impact, and an honest discussion of limitations).

Decision: Accept (Poster)