Topological Relational Learning on Graphs
Authors: Yuzhou Chen
Baris Coskunuzer
Yulia Gel
Venue: NeurIPS 2021 Poster (2021)
Keywords: Topological relational learning
Graph neural networks
Persistence based graph representation
Robust graph learning

Abstract: Graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. However, GNNs tend to suffer from over-smoothing problems and are vulnerable to graph perturbations. To address these challenges, we propose a novel topological neural framework of topological relational inference (TRI) which allows for integrating higher-order graph information to GNNs and for systematically learning a local graph structure. The key idea is to rewire the original graph by using the persistent homology of the small neighborhoods of the nodes and then to incorporate the extracted topological summaries as the side information into the local algorithm. As a result, the new framework enables us to harness both the conventional information on the graph structure and information on higher order topological properties of the graph. We derive theoretical properties on stability of the new local topological representation of the graph and discuss its implications on the graph algebraic connectivity. The experimental results on node classification tasks demonstrate that the new TRI-GNN outperforms all 14 state-of-the-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations, yielding up to 10\% better performance under noisy scenarios.

Topological Relational Learning on Graphs
Yuzhou Chen Department of Electrical Engineering Princeton University yc0774@princeton.ed
Baris Coskunuzer Department of Mathematical Sciences
University of Texas at Dallas
coskunuzuutdallas edu
Yulia R. Gel
Department of Mathematical Sciences University of Texas at Dallas and National Science Foundation yg @ll@uualllas...m edu
Abstract
Graph neural networks (GNNs) have emerged as a powerful tool for graph clas- sification and representation learning. However, GNNs tend to suffer from over- smoothing problems and are vulnerable to graph perturbations. To address these challenges, we propose novel topological neural framework of topological rela- tional inference (TRI) which allows for integrating higher-order graph information to GNNs and for systematically learning local graph structure. The key idea is to rewire the original graph by using the persistent homology of the small neigh- borhoods of nodes and then to incorporate the extracted topological summaries as the side information into the local algorithm. As a result, the new framework enables us to harness both the conventional information on the graph structure and information on the graph higher order topological properties. We derive thcoretical stability guarantees for the new local topological representation and discuss their implications on the graph algebraic connectivity. The experimental results on node classification tasks demonstrate that the TRI-GNN outperforms all 14 state-of- the-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations, yielding up 10% better performance under noisy scenarios.
Introduction
Node classification is one of the most active research areas in graph learning. The target here is, given a single attributed graph G and a small subset of nodes with prior label information, predict labels of all remaining unlabelled nodes. Applications of node classification are very diverse, ranging from customer attrition analytics to tracking corruption-come coniiiciinoiiiisiiinssii among politicians. Graph neural networks (GNNs) offer powerful machinery for addressing such problems on large heterogeneous networks, resulting an emerging field of geometric deep learning (GDL) which adapts deep learning to non-Fuclidean objects such as graphs 9
51 54 16].
Although GDL achieves a highly competitive performance in various graph-based classification and prediction tasks, similarly to the image domain deep learning on graphs is often found to be vulnerable graph perturbations and adversarial attacks [43 50 26) turn, most recent results 442 [9 suggest
that local graph information may be invaluable for robustifying GDL against graph perturbations and
adversarial attacks. Also, as shown by [36] 4 553 in conjunction with network community learning, local algorithms (i.e., algorithms based only on a small radius neighborhood around the node) may demonstrate superior performance if coupled with side information in the form of a node labeling positively correlated with the true graph structure. Inspired by these results, the ultimate goal of this
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

paper is to introduce the idea of local algorithms with local topological side information on similarity of node neighborhood shapes into GNN. By shape here. we broadly understand data characteristics which are invariant under continuous transformations such as stretching, bending, and compressing, and to study such graph shapes properties, we invoke the machinery of topological data analysis (TDA) 11
Topological Relational Inference: from Matchmaking to Adversarial Graph Learning and Be- yond In particular, to capture more complex graph properties and enhance model robustness, we introduce the concept of topologiaal relational inference (TRI) and propose two novel options for information passing which rely on the local topological structure of each node: (i) Inject new topology-inducee -nduuced multiedge between two nodes based on shape similarity of their local neighbor- hoods; (ii) Enrich each individual node features by harnessing local topological side information from its neighbors. The rationale behind our idea is multi-fold. First, we assess not only global graph topology and relationships between the feature sets of two individual nodes, as with the current diffusion mechanisms and random walks on graphs, but we also examine important interactions between shapes of the feature sets of the node neighborhoods. As a result, our new topology-induced multigraph representation (TIMR) of graph G in (i) strengthens the relationship among nodes which might not be (yet) connected by visible (or "tangible") edge in G but whose higher order intrinsic characteristics are very similar. The intuitive analogy here might be with a matchmaking agency who aims to connect two people a blind date, based on a careful assessment of interplay among similarities of their interests, aocio-demographice as well as that of their close friends, rather than bringing in two individuals together through random walk among all available profiles of potential candidates. Another example is the customer churn and retention analytics based on peer effects [15] That is, the goal here is to classify the node potential churn customer based not only the individual attributes but on interactions among its neighbor attributes. Second, such a new multiedge in (i), based on shape similarity of node local neighborhoods may assist not only the matchmaking agency in coupling the most appropriate individuals (or link prediction in less romantic and more technical terms). but to enhance resilience of the graph structure and associated graph learning. Indeed, a new multiedge in (i) can be used as an essential remedial ingredient in graph defense mechanisms as criteria to clean the perturbed graph, i.e., to reconstruct edges removed by the attacker or to suppress edges induced by the attacker, depending on the strength of the sopology-induce link. Third, by learning shape properties within each local node neighborhood. our TRI allows for systematic recovering of intrinsic higher-order interactions among nodes well beyond level of pair-wise connectivity, and such local topological side information (ii) enhances accuracy in node classification tasks even on clean graphs. Significance of our contributions are the following:
We propose a novel perspective to graph learning with GNN - topological relational inference, based on the idea of similarity among shapes of local node neighborhoods.
We develop a new appoloyyinnduced multigraph representation of graphs which systematically accounts for the key local information on the attributed graphs and serves as an important remedial ingredient against graph perturbations and attacks.
We derive theoretical stability guarantees for the new local topological representation of the graph and discuss their implications for the graph algebraic connectivity.
Our expansive node classification experiments show that TRI-GNN outperforms 14 state-of-the- art baselines on out 7 graphs and delivers substantially higher robustness (i.e., up 10% in performance gains under noisy scenarios) than baselines on all 7 datasets.
2 Related Work
Graph Neural Networks Inspired by the success of the convolution mechanism on image-based tasks, GNNs continue to attract an increasing attention in the last few years. Based on the spectral graph theory, [10) introduced graph- convolution in Fourier domain. However, complexity of this model very high since all Laplacian eigenvectors are needed. To tackle this problem, ChebNet [18] integrated spectral graph convolution with Chebyshev polynomials. Then, Graph Convolutional Networks (GCNs) of [00 simplified the graph convolution with a localized first-order approximation. More recently, there have been proposed various approaches based on accumulation of the graph information from a wider neighborhood, using diffusion aggregation and random walks. Such higher-order methods include approximate personalized propagation of neural predictions

---

(APPNP) B1I, higher-order graph convolutional architectures (MixHop) [3, multi-scale graph convolution (N-GCN) 2 and Lévy Flights Graph Convolutional Networks (LFGCN) [4]. In addition to random walks, other recent approaches include GNNs on directed graphs (MotifNet) 35 graph convolutional networks with attention mechanism (GAT, SPAGAN) [48 [2], and graph Markov neural network (GMNN) (39. Most recently, Liu et al. [34 consider utilizzig information on the node neighbors' features in GNN, proposing Deep Adaptive Graph Neural Network (DAGNN), However, DAGNN does not account for the important information on the shapes of the node neighborhoods.
Persistent Homology for Graph Learning Machinery of TDA and persistent homology (PH) is increasingly widely used in conjunction with graph classification, that is, when the goal is to predict a label for the entire graph rather than for individual nodes. Such tools for graph classification
with persistent topologiaa signatures include kernel-based methods [46] 40 33
[35] [2) and neural
networks [24 12 All of the above methods consider the task of classifying graph labels and are based on assessing 'global' graph topology, while our focus is node classification and our approach is based on evaluating local topological graph properties (i.e., shape of individual node neighborhoods). Integration of PH to node classification is virtually unexplored. To the best of our knowledge, the closest result in this direction is PEGN-RC (56). However, the key idea of PEGN-RC is distinctly different from our approach. PEGN-RC reweights only each existing edge, based on the topological information within its edge vicinity and, in contrast to TRI-GNN, neither compares any shapes, nor creates new removes existing edges. Importantly, PEGN-RC does not integrate topology of both graph and node attributes, while TRI-GNN does.
3 Preliminaries on Topological Data Analysis and Persistent Homology
The machinery of topological data analysis (TDA) and, particularly, persistent homology offer a mathematically rigorous and systematic framework of tools to evaluate shape properties of the observed data, that is, intrinsic data characteristics which are invariant under contimuous deformations
such as stretching, compressing, and bending [58] 21 37. The main premise is that the observed data which can be, as in our case, a graph G or a point cloud in a Euclidean or any finite metric space constitute discrete sample from some unknown metric space M.. Our goal is then to recover information on some essential properties of M which has been lost due to sampling. Persistent homology addresses this reconstruction task by counting occurrences of certain patterns, e.g.. loops. holes, and cavities, within shape of M. Such pattern counts and functions thereof, called topological signatures are then used to characterize intrinsic properties of g.
The approach is implemented in two main steps. We start from associating G with some nested sequence of subgraphs Gi C G2 C ... C 9m. G. Then we monitor evolution of pattern occurrences (e.g., cycles, cavities, and more generally n-dimensional holes) in this nested sequence of subgraphs. To ensure a systematic and computationally efficient manner of pattern counting, we construct a simplicial complex C₁ (e.g., a clique complex) induced by G. The sequence } induces a filtration: nested sequence of simplicial complexes C₁ C C2 S... S C.. C. Now we can not only track patterns but also evaluate the lifespan of each topological feature. Let b, be the index of the simplicial complex Co,, at which we first record (i.e., birth) the n-dimensional topological feature a (n-cycle), while simplicial complex Cd, be the first complex we observe its disappearance (i.e., death). Then lifespan or persistence of the topological feature o is d, by. To evaluate all topological features together, we consider persistence diagram (PD) where the multi-set records the birth and deaths of all n-cyclls in the filtration (C.). Here, A = {(L, 1)(4 E {R} is the diagonal set containing points in PD, counted with infinite multiplicity. Different persistent diagrams can be compared based on the cost of the optimal matching between points of the two diagrams, while avoiding topological noise near A
D, = {(br, d E TR2 d > bz)
Depending on the question hand, we can construct different suitable filtrations relevant to the problem. In this paper, we consider two different filtrations. First, we consider the sublevel filtration based on a node degree function f + N. As degree is an integer valued function, so are our thresholds {a:} } C N. Our sublevel filtration is then defined as follows. Let Va. = {u E V f(u)= S ). Then, G.; is the subgraph generated by V.,. In particular, the edge env E in Go, if both and u are in Vo.. We call this degree based filirution. In addition, we consider second filtration defined by the edge-wen weight function on the graph where edge weights are induced by similarity of node attributes. We call this attribute based filtration (See Section Note that degree based filtration
3

---

is induced only by the graph properties, while attribute based filtration is constructed by using the features coming from the observed data.
4 Topological Relational Inference Graph Neural Network (TRI-GNN)
Let g = (V,E) be an attributed graph with a set of nodes V. a set of edges E V V and Euy E denoting an edge between nodes u, v E V. The total number of nodes in G is N = [V] Let W E NNNN be a N x N-adjacency matrix of G such that wao = for euv E & and 0 otherwise, and D be diagonal N x N-degree matrix with Duu E. Wav For undirected graphs W is symmetric (i.e.. W W To feed in directed graphs into the graph neural network architecture, WC set W' = (W T + W)/2. Finally, each u E V is equipped with a set of node features, i..., X,, (Xu1, x2..... ..rr) represents an F-dimensional feature vector for node is a N x F-matrix of all node features. Our objective is to develop a robust semi-superrvied classifier such that can predict unknown node labels in 9, given some training set of nodes in g with prior labeling information. Figure Iillustrates our TRI-GNN model framework.
Problem Statement
V, and X
4.1 Topology-induced Multigraph Representation
The first step in our TRI model with the associated Topology-induced Multigraph Representation (TIMR) of G is to define topological similarity among two node neighborhoods. The key goal here is to go beyond the vanilla local optimization algorithms which capture only pairwise similarity of node features (36] and beyond only triangle motifs as descriptors of higher-order node interactions 335] 47). Our aim is to systematically extract all n--imensional topological features and their persistence in each node neighborhood and then to compare node neighborhoods in terms of their exhibited shapes.
Definition 1 (Weighted k-hop Neighborhood). An induced subgraph G (V%, S G. equipped with an edge-weight function induced by similarity of node features in gb. is called a weighted k-hop neighborhood of node u E V if: (1) for any E V the shortest path between u and v is at most k; (2) edge-weight function T : 14th x V* + Rz is such that for any 8, w E V with Cow E E Tow X X ||. where || || is either Euclidean distance (in the case of continuous node features), Hamming distance (in the case of categorical node features), Heterogeneous Value Difference Metric (HVDM) other distance appropriate for mixed-type data (20 If Tvu 1 for any Cowo E 9% reduces to a conventional k-hop neighborhood.
Armed with the edge-weight function r induced by node attributes (see Definition T or with a node degree function, we now compute sublevel filtration within each node neighborhood and track lifespan of each extracted topological feature, e.g., components, loops, cavities, and n-dimensional holes (see previous section). Here we consider two cases: attribute based filtration (G is equipped with an teight function T based on node attributes) and degree based filtration (g is an unweighted graph with 7 = 1). We can then compare how topologically similar shapes exhibited by node neighborhoods in terms of Wasserstein distance among their persistence diagrams.
Definition 2. (Topological Similarity among k-hop Neighborhoods) Let D(G)) and D(G.) be persistence diagrams of the weighted k-hop neighborhood subgraphs G:: and 9 of nodes u and v. re- spectively. We measure topological similarity between G and G.: with Wasserstein distance between the corresponding persistence diagrams as dw, (9t, 9b) = inf, (Ezedigguu ||x - >(x) where p 2 1 and 7 is taken over all bijective maps between D(G U A and D(G U A, counting their multiplicities. In our analysis we use p = 1.
As noted by 36) integrating neighboring nodes whose labeling is positively correlated with the true cluster structure, as a side information to a community recovery process may lead to substantial performance gains. Inspired by these results, we not only inject topological side information into GNN but also distinguish this side information w.r.t. its strength. We propose a new topology-induces multigraph representation of G. where a multiedge between nodes u and v comprises information on (tangible) connectivity between and u (i.e, existence of euv) as well as on strong and weak topological similarity of the local neighborhoods u and v, irregardless whether euv exists.
Definition 3. (Topology-induced Multigraph Representation (TIMR) Consider a graph G (V, E), with dw,p G as measure of topological similarity among two k-hop neighborhoods

---

1111
Original Graph g
TRI-GNN Conv Layer
Wiopo
Softmax
Labels
STAN
Missope
Figure The TRI-GNN semi-supervised learning framework (for more details see Appendix B).
Gh and ghh for all u, V (see Definition 1.. Then topology-induced multigraph representation
of G is defined as Q = (V, goopo,, where glopa a set multiedges such that for any u, v E V and thresholds c2 R+
Cuv = eus Ec; (1 -1 (G..)
(1)
Note that (dw.p(9t, g E [0] and (dw.p(9H 9 E [<2, [2)) are incompati- ble events. Hence, multiedges have multiplicity at most and Etopo is multiset of {(1, 0); (0, 1, 1): (1,0, 1);; (0, 1)}. The intuition behind TIMR to reflect a level of shape similarity among any
node neighborhoods, irregardless whether there exists an edge between these nodes in G. Later, by using Ω we induce graph Wtepo (Figure 1 defined as follows: If neighborhoods of two nodes in topologically similar, add edge between the nodes there is none. If neighborhoods of two nodes in G are topologically dissimilar, we remove the edge between the nodes if one exists.
Alternatively, we can associate TIMR with positive topology-induced and negative lopology-induced adjacency matrices, Wioopo and Vrtopo respectively
Wrtopo = 10 W.p (G ) <g),
Wotopo = [c2 < K. gt) < oo),
(2)
where [:] is an Iverson bracket, i.e., whenever condition in the bracket satisfied, and otherwise. Selection of hyperparameters é and 62 can be performed by assessing quantiles of the empirical distribution of shape similarities and then voos-valiiation. Thresholds 6 and C2 are used to reinforce meaningful edge structures and suppress noisy edges.
How does TIMR help? TIMR allows not only inject of their multi-hop neighborhoods are sufficiently close, but also to eliminate an existing edge topological distance among their multi-hop node neighborhoods is higher than predefined threshold 62. That is, TIMR adds an edge between the nodes whose "similarity" is detected by persistent homology, and removes the edge between "topologically dissimilar" nodes. This way, in the new TIMR graph, similar nodes gets closer, and dissimilar nodes gets farther away, thereby assisting throughout the node classification process. As result, TIMR also mitigates the impact of noise edges and reduces the effect of over-fitting. Furthermore, while we have not formally explored TIMR in conjunction with formal defense mechanisms against adversarial attacks, TIMR may be viewed as essential remedial ingredient in defense. Indeed, TIMR offers an insight about one of the key defense challenges (27], namely, systematic criteria we should follow to clean the attacked graph TIMR suggests to recover edges removed by the attacker with positive oopology-induca links and to suppress edges induced by the attacker with negative topology-induced links.
edge among two nodes if shapes
TIMR Theoretical Stability Guarantees
We now establish theoretical stability properties of the TIMR average degree. The average degree
17 I and, hence, Here we prove that under perturbations of the observed graph G, average degrees of the TIMR graphs the original and distorted copies remain close. That is, the proposed TRI framework allows us to increase robustness
known to closely related to performance node classification tasks 28
degree-dependent regularization is often used in adversarial training [8
49 44
5

---

of the graph degree properties with respect to graph perturbations and attacks. Given that persistent homology representations are known be robust against noise, our result appears to be intuitive. However, integration of graph persistent homology into node classification tasks and its theoretical guarantees remain yet an untapped area.
Let G and G- be two graphs of the same order. Let T and T be TIMR graphs of G and g constructed by the degree based filtration. We define local k-distance between two graphs based on the Wasserstein distance dw, between their persistence diagrams as follows. Let w= be node in g and g be k-neighborhood of the u- in g Let
d (ut u dw, (Do (o(C
where dw, is Wasserstein-1 distance (see Definition 1. and DG is the persistence diagram of O-cycles. Let p V+ + V be bijection between node sets of G and g respectively. Then, the local k-distance between G and G is defined
(" g min Eda(ut dalut (p("))
We now have the following stability result:
Theorem (Stability of Average Degree). Let G+ and g be two graphs of same size and order. Let T be the TIMR graph induced by g with thresholds e and e2. Let a the average degree of T Then, there exists a constant K (2)
such that
la+ a= K(1,, (2))
The proof of the theorem given Appendix the supplementary material.
Furthermore, we conjecture the following result on stability of algebraic connectivity of TIMR graphs for the attribute based case. Here, the algebraic connectivity A2 the second smallest eigenvalue of the graph Laplacian L(G), and it is considered to be spectral measure to determine the robustness of the graph 45
Conjecture: Let G be graph, and let G' be a graph which is obtained by adding one edge e to G. i... g' UUe. Let T" be the TIMR graphs induced by G. g', respectively. Then,
D22(T') x2() < (2) >z(9))-
Note that this conjecture not true for degree based TIMR graphs. The reason for that when one adds an edge evv to G. then this operation significantly changes t-heighborhoods of all nodes in N& (1:) and (. Since degree based TIMR construction depends on persistence diagrams of these k-neighborhoods, adding such edge causes uncontrollable effect the algebraic connectivity. However, in attribute based construction, similarity is only based on the attributes, and the distances in the graph does not have effect edge addition/deletion decision. So, when the original graph G is perturbed by adding an edge, the attributes remain intact, and TIMR representations of the original and perturbed graphs identical.
4.3 STAN: learning from Subgraphs, Topology and Attributes of Neighbors
For graphs with continuous or binary node features, higher-order form of message passing and aggregation (i.e., powers of the adjacency matrix) are shown to capture important structural graph properties that are inaccessible the node-level. However, such higher-order architectures largely focus global network topology and do not account for the important local graph structures. Also, performance such higher-order graph convolution architectures tend to suffer from over-smoothing and be susceptible noisy observations, since their propagation schemes recursively update each node's 's feature vector by aggregating over information delivered by all further nodes captured by random walk.
Here we propose new recursive feature propagation scheme STAN which updates the node features from Subgraphs, Topology, and Attributes of Neighbors. In particular, for each target node, STAN (i) converts these three features into form of topological edge weights, (ii) calculates topological average of neighborhood features, (iii) aggregates them with the initial node features.

---

Let x = X. be the initial node features for E V and T be the number of STAN iterations. Then we iteratively update the feature representation node u using side information collected from nodes within its k-hop local neighborhood via X Sup (nnerr (x 1 c((u) EveVi(a) duo x
where fup is the update function such multi-layer perceptron (MLP) and gated network, Paggr is function that aggregates topological features into node features, such as sum and mean; or(u) is weighting factor which can be set either as hyperparameter or fixed scalar, and duo are normalized topological edge weights
exp [dd (9 (.)) (w))
duv E EnEVs( exp (( (9u: ).))
The core principle of STAN to assign different importance scores to nodes, depending on how similar topologically their neighborhoods are the target node, and to control the impact the target node prediction when aggregating neighborhoods information. For instance, suppose target node is and we also have nodes and We assign higher weight to the edge between u and (if the shapes of their neighborhoods are more similar) and a lower weight to the edge between u and w (if neighborhoods of and have distinct topology). As result, the updated node features of u will be more affected by v.
STAN
Tratuno
from 2-hop Neighbern
Aguragtiznn
Eaieting
X
Figure STAN node feature vectors extension. The target node (red) with 2-hop neighborhood. where four 1-hop neighbors (blue) and three 2-hop neighbors (green). Each node is represented by 3-component feature vector. We include more discussion on the STAN in Appendix B.
4.4 Convolution based TRI-GNN Layer
We now turn construction of the TRI-GNN layer. Let W NxNx3 be a 3-dimension tensor, where N is the number of nodes and 3 is the number of candidate adjacency matrices (i.c., W, Whoppo and Wioppo" ). Let W uer be the r-th type of edge between nodes and of W, where ( NN. [N, and E (1,2, That is, we denote W, Wrupo and Wiopo by adjacency matrix Wripoo
setting r 1,2, We then consider a joint topology-indieeee
f1, if Σ, W wer > 0
W Wolopo
otherwise
In the experiments, utilize the classification function for the generalized semi uemi-supervieed learning as the default filter engine of TRI-GNN. Given Wrippo we compute topological distance-based graph Laplacian Looo = (Diopo) - - Tiropo (Diopogo-1 where Viroopo = (W"oope + I)e, Dtope Σ. W-topo E [0, 1]. and p E (0, oc). Equipped with the graph Laplacian Lope and node information matrix (T) at iteration T. TRI-GNN uses the following graph convolution layer
((+1)) = (μ - -1 ((0000) =
(uLinn) H()
where (0, 1] is regularization parameter, (()) E NXF, and H(++1) NxF+++ are input and output activations for layer (H) x())), O E Fix are the trainable parameters of

---

TRI-GNN, and &b is an element- wise nonlinear activation function such as ReLU, In the experiments j is selected from {0.1, 0.2, .... 0.9... and its choice impacts the number of terms in Taylor expansion. To reduce the computational complexity, based on the Taylor series expansion, we empirically find that max; = [RR,] is a suitable rule of thumb (where R. E [2, 20)) while the closer more robust to the choice of regularization parameters the performance is. Note that in order to improve the robustness of TRI-GNN when it is exposed to noisy, we can consider convolution based TRI-GNN layer with parallel structure.
to O, the
Table 1: Performance on semi-supervised classification. Average accuracy (%) and standard deviation
(6) in ()
Method
IEEE 118-Bus
ACTIVSg200
ACTIVS
ACTIVS22000
Cora-MII
CiteSeer
PubMed
ChebbNet
(3.11)
80.63 (4.20)
95.18(1.00)
80.04 (0.37)
(1.21)
70.23 (0.80)
78.40
GCN
52.86 (0.78)
82.96 (1.66)
90.33 (0.68)
73.36 (0.41)
81.50 (0:40)
71.11 (0.72)
79.00 (0.53)
MoufNee
65.75 (0.77)
13.20(1.6)
95.18 (0.53)
82.00 (0.44)
ARMA
70.55 (2.23)
80.07 (3.30)
(0.47)
81,20 (0.23)
(0.63)
(0.44)
(D.30)
GAT
(1.80)
83.56 (2.58)
(0.40())44)
83,00 (0.59)
83,11 (0.70)
70.85 (0.70)
78.56 (0.31)
RGCN
81.80 (1.79)
83.35 (3.12)
95.91 (0.50)
85.23 (0.40)
82.80 (0.60)
72.13 (0.50)
79.11 (0.30)
GMNN
78.88 (2.50)
84.13 (1.89)
96.57 (0.52)
86.21 (0.29)
83,72 (0.90)
73.10 (0.79)
81,80 (0.53)
LGCNS
71.43 (2.20)
83.78 (1.50)
95.14 (0.45)
85.57 (0.25)
83.35 (0.51)
73.08 (U.63)
79.51 (0.22)
SPAGAN
78.55 (2.25)
81.83 (2.09)
96.19
86.00
83.63 (0.55)
73.02
79.60 (0.40)
APENP
82,05 (2.24)
81.21 (1.85)
96.11(0.45)
86.77 (0.30)
K3.31 (0.53)
72.30 (U.51)
80.12 (0.20)
82.19 (2.20)
79.89
(0.50)
86.87 (0.33)
(0.57)
71.40 (0.32)
79.60 (0.39)
LEGCN
(2.30)
81.11 (2.10)
97.61 (0.47)
87.74 (0.30)
84.35 (0.57)
71.89 (0.77)
79.60 (0.55)
MixHop
80.05 (2.50)
80.53 (1.96)
95.94 (0.40)
86.10 (0.25)
81 (0.81)
71.41 (0:40)
80.81 (0.58)
PEGN-RC
(1.90)
83.30 (1.100
97.20 (0.50)
87.62 (0.74)
82.70 (0.50)
71.91 (0.63)
79:40 (0.70)
TRI-GNNA
82,80 (1.64)
84.93 (1.51)
97.85 (U.56)
88.82 (0.56)
84.80 (0.55)
73,45 (0.65)
79.80 (0.52)
TRI-GNN)
82.67 (2.08)
86.18 (0.20)
98.11 (0.43)
89.06 (0.44)
84.98 (0.49)
73.32 (0.48)
79.70 (0.50)
5 Experiments
We now empirically evaluate the effectiveness of our proposed method on seven node-classification benchmarks under semi-supervised setting with different graph size and feature type. We run all experiments for 50 times and report the average accuracy results and standard deviations.
5.1 Experimental Settings
Datasets We compare TRI-GNN with the state-of-the-an (SOA) baselines, using standard publicly available real and synthetic networks: (1) 3 citation networks [4]]: Cora-ML, CiteSeer, and PubMed, where nodes are publications and edges are citations; (2) 4 synthetic power grid networks (8) 7 23 IEEE 118-bus system, ACTIVSg200 system, ACTIVSg500 system, and ACTIVSg2000 system, where each node represents a load bus, transformer, generator and we use total line charging susceptance (BR_ B) as edge weight. For more details see Table I (in Appendix C.I).
Baselines We compare TRI-GNN with 14 SOA GNNs: (i) 5 higher-order graph convolution architec-
tures: LGCNs 222 APPNP BT, VPN (25. LFGCN [14, and MixHop []: (ii) 2 graph attention
mechanism: GAT (48 and SPAGAN [5]; (iii) 4 GNNs with polynomial filters: ChebNet [18),
GCN 30 MotifNet (35], and ARMA [6] (iv) GNNs by learning the generative distribution:
GMNN 39 and RGCN [57; and (v) I GNNs with topological information: PEGN-RC (56). In the
experiments, we implement two variants of TRI-GNN, i.e., TRI-GNNA (node attributes as filtration function) and TRI-GNN, (node degree filtration function). In addition, in robustness experi- ments, we select the 4 strongest basclines in each of the GNN areas: random walks, graph attention networks, higher-order graph convolutional models, and robust graph convolutional networks (i.c., APPNP, GAT, LFGCN, and RGCN). More details on experimental setup are in Appendix C.2. The source code of TRI-GNN is publicly available at https:///itthut: com wow./RRR............ CAAI--NNTTRRE. GNN git
5.2 Performance on Node Classification
Table shows the results for node classification results on graphs. We observe that TRI-GNN outperforms all baselines on CoraML, CiteSeer, and four power grid networks, while achieving comparable performance on PubMed. This consistently strong performance of TRI-GNN indicates utility of integrating more complex graph structures through aggregating higher-order topological
8

---

information. The best results are highlighted in bold for all datasets. As Table[sshwws TRI-GNND and TRI-GNN, outperform all baselines on all 7 but benchmark datasets, yielding relative gains of 0.5-2.5% on clean graphs. Overall, TRI-GNND appears to be the most competitive approach, especially for ACTIVSg200 and ACTIVSg500 systems. Nevertheless, TRI-GNNA tends to follow TRI-GNND relatively closely. It validates that the framework of topological relational inference can integrate topological information across multigraph representation and feature propagation, respectively. On PubMed, GMNN achieves a better accuracy than both TRI-GNN versions due to PubMed exhibiting the weakest structural information with very few links per node on average, but both TRI-GNN models still deliver highly competitive results. In addition, heterogeneous graphs, with lower numbers of node attributes per class, richer topological structure (i.e.. synthetic ACTIVSg200 and ACTIVSg2000) and weaker dependency between attributes and classes, PH induced by the graph properties is more important than atribbat-induceed PH, while for denser, more homogeneous graphs IEEE 118-bus, attribute-based filtration is the key. These insights echo findings in real citation networks.
find that for sparser
Ablation Study Our TRI framework contains two key components: (i) encoding higher-order topo- logical information via TIMR, (ii) STAN, i... updating the node features by aggregating information from subgraphs, topology, and neighborhood features. To glean deeper insight into how different components help TRI-GNN to achieve highly competitive results, we conduct experiments by re- moving individual component separately. namely (1) TRI- TRI-GNND w/o TIMR (i.e., denoted by Ω2), (2) TRI-GNND w/o STAN, and (3) TRI-GNND with TIMR and STN (where STN represents updating the node features by only aggregating information from subgraphs and topology without neighborhood features). As Table2i shows, both TIMR Ω and STAN indeed yield significant performance improve- ments all datasets. The ablation study contribution of TIMR and STAN with TRI-GNNA are in Table II of Appendix C.3. The results show that all the components are indispensable.
Table 2: TRI-GNND ablation study. Significance analysis is performed with one-sided two-sample t-test based on 50 runs; * ** *** denote p-value < 0.1, 0.05, 0.01 (i.e., significant, statistically significant, highly statistically significant).
Dataset
TRI-GNND
w/o Ω
w/o STAN
with Q STN
ACT1VSg200
86.18 (0.20)
**82.93 (1.32)
***8300 (3.17)
g3.25. (1.58)
ACTIVSg500
98.11 (0.43)
9**93.71 (1.03)
***94.31 (1.20)
9**93.69 (1.50)
Cora-ML
84.98 (0.49)
**8.226 (0.77)
***84.00 (0.33)
*** *4.4000 (0.56)
CiteSeer
73.32 (0.48)
**73.11 (0.43)
73.20 (0.55)
*73.19 (0.47)
Boundary Sensitivity We select the el and e2 values based on quantiles of Wasserstein distances between persistence diagrams (see Figure [3a]. The optimal choice of e and e2 can be obtained via cross-validation. For instance, the optimal quantile of E1 and 62 for ACTIVSg200 dataset is 0.55 and 2.50 respectively. We consider the lower and upper bounds for é1 are 0.50 (minimum) and 0.05-quantile, respectively, and the lower and upper bounds for e2 are 0. Iqqunnit and 6. 7. (maximum), respectively. For E1, we generate a sequence from 0.50 to 2.00 with increment of the sequence 0.05; for c2. we generate a sequence from 2.50 to 6.74 with increment of the sequence 0.5. Based on cross- validaaoi,,,,,,,, we conduct experiments in different 61 and 62 combinations. Figures (3b] 3nd show the performances with respect to different thresholds (c1 and c2) combinations (where t denotes the (where i E {1, 2)) is not fixed). From the results in Figure 3 we find that (e1, around (0.55, 2.50) tend to deliver the optimal performance (accuracy (%)) The optimal results differ among graphs and depend on sparsity, label rates and graph higher-order properties. To better examine the boundary sensitivity, we further evaluate hyperparameters E and E2 on ACTIVS3500 in Appendix C.8.
Robustness Analysis To evaluate the model performance under graph perturbations, we test the robustness of the TRI-GNN framework under random attacks (here we present the results for TRI- GNNA, and analogous robustness for TRI-GNN, are in Appendix C.4.). Random attack randomly generates fake edges and injects them into the existing graph structure. The ratio of the number of TRI-GNNA
fake edges to the number of existing edges varies from 0 to 100% As consistently outperforms all baselines on both citation and power grid networks under random attacks, delivering gains up to 10% in highly noisy scenarios (see Cora-MI.). These findings indicate that TRI-GNNA is again the most robust GNN node classifier under random attacks. By aggregating local

---

13.0
O5 CI
(a) Wasserstein distances.
(b) (cr, (2).
(c) (c),
Figure 3: Hyperparameters e₁ and selection of TRI-GNN on ACTIVSg200 dataset.
topological information from node features and neighborhood substructures, TRI-GNNA a can "absorb" noisy edges and, as result, exhibits less sensitivity to graph perturbations and adversarial attacks.
ACTiVS-500
ACTVV522000
Cera-NL
1.00
4.55
675
645
Rado ddges
Naton Edges
Radoo
dies
Radio Make Edges
Figure Node classification accuracy under random attacks.
Computational Costs In less extreme scenarios, the expected number nodes in the k-hop neigh- borhood can be approximated by dh. where d is the mean degree of the graph and mathematical expectation is in terms of the node degree distribution. The computational complexity for Wasserstein distance between twO persistence diagrams is ((MS), where M is the total number of barcodes in the both persistence diagrams. In the worst case scenario, we use very fine filtering function for persistence diagrams of k-hop neighborhoods, it would give at most 2d barcodes (i.c., the number of barcodes in each k-hop neighborhood is at most d' and we compare two k-hop neighborhoods). Considering use the degree filtering function for our persistence diagrams, we expect to have much less (~ d barcodes in the 0-th persistence diagram of k--hpp neighborhood by using the technique in [29] Hence, the overall computational complexity would be of stochastic order 2N ). It may be costly to run PH for denser graphs (currently, computational complexity is the main roadblock for all PH-based methods graphs) but noted earlier, for denser graphs may filtration under lower k-hops which is still found to be very powerful even for small Table II in Appendix C.2 reports the average running time of PD generation and training time per epoch of our TRI-GNN model on all datasets.
degree
Conclusion
We have proposed novel perspective to node classification with GNN, based on the TDA con- cepts invoked within each local node neighborhood. The new TRI approach has shown to deliver highly competitive results clean graphs and substantial improvements in robustness against graph perturbations. the future, we plan to apply TRI-GNN as a part of structured graph pooling.
Societal Impact and Limitations
Among the major limitations we currently see is probable existence of the bias of the proposed node classification approach due to potentially unbalanced population groups [5]. Indeed, in the context of social data analysis, given that we analyze peer neighborhoods which themselves tend to be largely formed by the same users as the target node and hence are likely to dominated by the abundant group, such bias is very likely to exist and to be nen-neglig Mitigating it is problem on its own but some ideas include using multiple filtration functions based on different node attributes so the node neighborhoods are made more diverse and are no longer dominated by specific group or removing some potentially sensitive node attributes (e-g., gender) completely from the study (which has its own pros and cons in terms of accuracy).
10

---

Acknowledgements
This work sponsored by the National Science Foundation under award numbers ECCS 2039701, INTERN supplement for ECCS 1824716, DMS 1925346 and the Department of the Navy, Office of Naval Research under ONR award number N0001421 12226. Part this material is also based upon work supported by (while serving at) the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation and/or the Office of Naval Research. The authors are also grateful to the NeurIPS anonymous reviewers for many insightful suggestions and engaging discussion which improved clarity of the manuscript and highlighted new open research directions.
References
[1] Emmanuel Abbe, Enric Boix-Adsera, Peter Ralli, and Colin Sandon. Graph powering and spectral robustness. SIAM Journal on Mathematics of Data Science, 2(1):132-157, 2020.
[2] Sami Abu Abb-EElHHaie -l-HHiiaaa, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN: Multi-scale graph convolu- tion for semi suiisvuere node classification. In UAI, pages 841 851, 2020.
[3] Sami -a--aa- Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML. pages 21-29, 2019.
Konstantin Avrachenkov and Maximilien Dreveton. Almost exact recovery in noisy semi-supervised learning. arXiv:2007. 14717, 2020.
[5] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning. fairmlhook.org. 2021. http::/www fairmlbook. org
[6] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. TPAMI, 2021.
Adam B Birchfield, Kathleen M Gegner, Ti Xu, Komal S Shetye, and Thomas J Overbye. Statistical considerations in the creation of realistic synthetic power grids for geomagnetic disturbance studies. Transactions on Power Systems, 1202):1502-1510, 2016.
[8] Adam B Birchfield. Ti Xu, Kathleon M Gegner, Komal S Shetye, and Thomas Overbye. Grid structural characteristics validation criteria for synthetic networks. Transactions Power Systems, 32(4):3258- 3265, 2016.
[9] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. Signal Processing Magazine, 34(4):18-42 2017.
[10] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[11] Gunnar Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:289-368, 2014.
[12] Mathieu Carrière, Frédéric Chazal, Yuichi Ike. Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In A/STATS, pages 2786-2796, 2020.
[13] Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in Artificial Intelligence, 4, 2021.
[14] Yuzhou Chen, Yulia R Gel, and Konstantin Avrachenkov. LFGCN: Levitating over graphs with levy flights. In ICDM, pages 960-965. IEEE, 2020.
[15] Yuzhou Chen, Yulia Gel, Vyacheslav Lyubchich, and Todd Winship. Deep ensemble classifiers and peor effects analysis for churn forecasting in retail banking. In PaKDD, pages 373-385, 2018
[16] Zhiqian Chen, Fanglan Chen, Lei Zhang, Taoran Ji, Kaiqun Fu, Liang Zhao, Feng Chen, and Chang- Tien Lu. Bridging the gap between spatial and spectral domains: A survey on graph neural networks. arXiv:200.11887. 2020.

---

[17] Hanjun Dai, Hui Li. Tian Tian, Xin Huang. Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In ICML, pages 1115-1124, 2018.
[18] Michaël Defferard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NeurIPS, pages 3844-3852, 2016.
[19] Tyler Derr, Yao Ma, Wenqi Fan, Xiaorui Liu, Charu Aggarwal, and Jiliang Tang. Epidemic graph convolutional network. In WSDM, pages 160-168, 2020.
[20] Michel Marie Deza and Elena Deza. Encyclopedia of distances. In Encyclopedia Distances, pages 1-583. Springer, 2009.
[21] Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010.
[22] Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale leamable graph convolutional networks. In ACM SIGKDD, pages 1416-1424, 2018.
[23] Kathleen M Gegner, Adam Birchfield, Xu, Komal Shetye, and Thomas Overbye. methodology for the creation of goographically realistic synthetic power flow models. In PECI, pages 1-6. IEEE, 2016.
[24] Christoph D Hofer. Roland Kwitt, and Mare Niethammer. Learning representations of persistence barcodes. JMLR, 20(126): 2019.
[25] Ming Jin, Heng Chang, Wenwu Zhu, and Somayeh Sojoudi. Power up! robust graph convolutional network via graph powering. In AAAI, 2021.
[26] Wei Jin, Yaxing Li, Han Xu, Yigi Wang. Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review, a tool and empirical studics. ACM SIGKDD Explorations Newsletter, page 19 34, 2021.
[27] Wei Jin, Yao Ma. Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In ACM SIGKDD. 2020.
[28] Antony Joseph and Bin Yu. Impact of regularization on spectral clustering. The Annals of Statistics, 44(4):1765-1799 2016.
[29] Lida Kanari, Adélic Garin, and Kathryn Hess. From trees to barcodes and back again: thcoretical and statistical perspectives. Algorithms, 13(12):335, 2020.
[30] Thomas N Kipf and Max Welling. Supervupe classification with graph convolutional networks. In ICLR, 2017.
[31] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ICLR, 2019.
[32] Panagiotis Kyriakis. Iordanis Fostiropoulos, and Paul Bogdan. Learning hyperbolic representations of topological features. In ICLR, 2021.
[33] Tam and Makoto Yamada. Persistence fisher kernel: riemannian manifold kernel for persistence diagrams, In NeurlPS, pages 10007-10018, 2018
[34] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. ACM SIGKDD, pages 338-348, 2020.
[35] Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a botif-based graph convolutional network for directed graphs. In DSW, pages 225-228. IEEE, 2018
[36] Elchanan Mossel and Jiaming Xu. Local algorithms for block models with side information. In ITCS, pages 71-80, 2016.
[37] Elizabeth Munch. A user's guide to topological data analysis. Journal of Learning Analytics, 4(2):47-61, 2017.
[38] Sharad Nandanwar and M Narasimha Murty. Structural neighborhood based classification of nodes in a network. In ACM SIGKDD, pages 1095-1094, 2016.
[39] Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph markov neural networks. In ICML, pages 0241-5250, 2019.
12

---

[40] Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lhhman procedure for graph classification. In ICML, pages 5448-5458, 2019.
[41] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93- 93, 2008.
[42] Ke Sun, Piotr Koniusz, and Zhen Wang. Fisher-bures adversary graph convolutional networks. In UAI, pages 465-475. PMLR, 2020.
[43] Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, and Bo Li, Adversarial attack and defense on graph data: A survey. arXiv:1812.10528, 2020.
[44] Yiwei Sun, Suhang Wang. Xianfeng Tang, Tsung-Yu Yu Hsieh, and Vasant Honavar. Non-target-speeific node injection attacks graph neural networks: A hierarchical reinforcement learning approach. In WWW, volume 3, 2020.
[45] Ali Sydney, Caterina Scoglio, and Don Gruenbacher. Optimizing algebraic connectivity by edge rewiring. Applied Mathematics and Computation, 219(10):5465-5499 2013.
[46] Mattco Togninalli, Elisabetta Ghisu, Felipe LJinares-Lépez, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kerelss. NeurlPS, pages 6439-6449, 2019.
[47] Francesco Tudisco, Austin R Benson, and Konstantin Prokopchik. Nonlinear higher-order label spreading. In www. pages 2402-2413, 2021.
[48] P. Veličković, G. Cucurull, A. Casanova, A. Romero, Lio, and Y. Bengio. Graph attention networks. In ICLR, 2018.
[49] Shen Wang, Zhengzhang Chen, Jingehao Ni, Xiao Yu, Zhichun Li, Haifeng Chen, and Philip S Yu. Adversarial defense framework for graph neural network. /rXiv:9905.03679 2019.
[50] Huijun Wa, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack defense. In IJCAI, 2019.
[51] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chenggi Zhang, and Yu Philip. comprehen- sive survey on graph neural networks. TNNIS,, 2020.
[52] Yiding Yang, Xinchao Wang, Mingli Song. Junsong Yuan, and Dacheng Tao. SPAGAN: shortest path graph attention network. ICCAI, pages 4099-4105, 2019.
[53] Monisha Yuvaraj. Asim K Dey, Vyachcslav Lyubchich, Yulia Gel, and H Vincent Poor. Topological clustering of multilayer networks. Proceedings of the National Academy of Sciences, 118(21), 2021.
[54] Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: survey. TKDE, 2020.
[55] Qi Zhao and Yusu Wang. Learinng metrics for persistence-base summaries and applications for graph classification. In NeurlPS, pages 9859-9870, 2019.
[56] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In AISTATS. pages 2906. PMLR, 2020.
[57] Dingyuan Zhu, Ziwei Zhang. Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In ACM SIGKDD, pages 1399-1407, 2019.
[58] Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geumetry, 33(2):249-274, 2005.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes] See Section 5.2, scalability.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4.2.
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Material, Appendix A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material
URL)? [Yes] See
Section 5 and Appendix C. Source code and data are publicly available at https git
//github.
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5 and Appendix C.
(c) Did you report error bars (e.g., with respect to the random seed after running ex- periments multiple times)? [Yes] See Section 5 and results on statistical hypothesis testing-
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5 and Appendix C.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ofmNtrdKQzD", "reviewer": "Reviewer_uhB4", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "## Strong points\n\n- 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. \n- 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). \n- I appreciate the authors have added an ablation study, which clearly identifies the source of the improvements. \n- 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. \n- The robustness analysis nicely complements the theoretical results on stability to perturbations. \n- Figure 1 does a good job of illustrating how the different pieces are coming together. \n\n## Improvements\n\n- 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. \n- The presentation of the paper can be improved from many points of view:\n  - 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. \n  - 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. \n  - 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.\n  -  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. \n - 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. \n- 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. \n- I believe the computational complexity of the method was not stated. \n- Nit: Another topological approach for higher-order interactions which is not cited was introduced in https://arxiv.org/abs/2103.03212. \n\nEDIT: After discussion, I decided to raise my score from 6 to 7. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not included a section on limitations and societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "EDIT: I have edited my response to flag the need for ethical review based on the motivating applications discussed by the authors, which might raise certain ethical issues. ", "needs_ethics_review": "Yes", "ethics_review_area": ["Inappropriate Potential Applications & Impact  (e.g., human rights concerns)"], "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "nWiypJN3WV", "reviewer": "Reviewer_BcEA", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "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.\n\nSignificance: A nice attempt to better utilize local topological information. Derive theoretical stability guarantees for the new local topological representation of graph.\n\nQuality: 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.\n\nClarity: 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? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "23"}, "extra_text": {}}, {"review_id": "a_jvdIP7By", "reviewer": "Reviewer_srjf", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "-- Strengths:\t\n1. Induces topological information from the node neighborhood by adding/deleting edges that are topologically similar/dissimilar\n\n2. Learns node features from the edges weighted by the topological distance, thus introducing an attention over the neighbourhood based on topology\n\n3. The proposed method performs well in comparison to the baselines\n\n-- Weaknesses:\t\n1. 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.\n\n2. 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.\n\n3. 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. \n\n4. 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. \n\n5. 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:\n“New Benchmarks for Learning on Non-Homophilous Graphs” - Lim et. al (WWW’21).\n\n6. 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.\n\n7. 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? \n\n8. 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. \n\"Towards More Practical Adversarial Attacks on Graph Neural Networks\" - Ma. et. al. (NeurIPS 20).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There was no societal impact section in this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}, {"review_id": "IWBhMicm06", "reviewer": "Reviewer_oJSD", "summary": "The work proposes an extension to conventional graph neural networks by\nincorporating additional information about local topological structures in the\nproximities of nodes.  The core contribution of the work is to additionally\nallow rewiring of the graph based on the similarities of topological structures\nof pairs of nodes.  It is shown that these rewirings can lead to increased\nrobustness of models against graph perturbations or adversarial attacks.  The\nmodel is evaluated on a series of Node Classification tasks and is shown to\nhave favorable performance compared to many baselines.\n", "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": "The work is well written and motivated and the paper is well structured.\nExperiments are detailed and ablations are preformed to show the contribution\nof individual model components (where some improvements could be made, see\nmajor comment 1).  I have some concerns with regard to reproducability of the\nresults as hyperparameters are not exactly documented, further I am unable to\nverify the selection process of hyperparameters (major comment 2).\n\nGenerally, the approach is novel and can represent a promising direction for\nintegrating aspects from topological data analysis into a Graph Neural\nNetworks.  \n\nMajor comments:\n 1. Removing individual components of the model can significantly impact the\n    expressiveness of a model.  I would recommend to instead of removing the\n    components, to implement fake versions which do not actually rely on PH.\n    In the case of the TIMR ablation one could for example use random features\n    as the basis of distance computations between nodes.  Without such\n    ablations it is hard to tell if the reduced performance is due to lower\n    model expressivity or due to the removal of the component.\n 2. The search of hyperparameters seems to be largely limited to the presented\n    method, which can give the approach a competitive advantage.  Further, the\n    exact procedure for deriving the hyperparameters is not entirely clear.\n    Which metric was used for deriving the best hyperparametes? Which ranges\n    were evaluated?  Was the metric computed on a held out validation set or via\n    cross validation?  What are the exact hyperparameters used for each model?\n    The details are crucial to asses the study design and to estimate how\n    representative the performance of the model is and pinpoint potential\n    biases.\n\nMinor comments:\n 1. The graph corruption experiment could be extended to also incorporate\n    corruption of node features.  While this is not covered by the stability\n    theorem, it would still be interesting to see how the models perform based\n    on different perturbations of the input.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not addressed the social impact of their work.  While I think\nthat the implications are of limited degree, there are some potential\ndirections that could be mentioned here.  In particular, graph algorithms for\nnode classification can be used to categorize people using observational data\nand include how they interact with others.  While this can\nmostly be used for the good of developing better products or offering targeted\nadvertisement, it could also be used in surveillance systems where the social\nimplication would be non-negligible.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)