Topological Relational Learning on Graphs
Year: 2022

Abstract:
Graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. However, GNNs tend to suffer from oversmoothing 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 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 theoretical 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 new TRI-GNN outperforms all 14 state-ofthe-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations, yielding up to 10% better performance under noisy scenarios.

heading: 1 Introduction
text: 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, to predict labels of all remaining unlabelled nodes. Applications of node classification are very diverse, ranging from customer attrition analytics to tracking corruption-convictions among politicians. Graph neural networks (GNNs) offer a powerful machinery for addressing such problems on large heterogeneous networks, resulting in an emerging field of geometric deep learning (GDL) which adapts deep learning to non-Euclidean 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 to graph perturbations and adversarial attacks [43, 50, 26]. In turn, most recent results [42, 19] suggest that local graph information may be invaluable for robustifying GDL against graph perturbations and adversarial attacks. Also, as shown by [36, 4, 53] 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 (NeurIPS 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) [21, 11].
Topological Relational Inference: from Matchmaking to Adversarial Graph Learning and Beyond In particular, to capture more complex graph properties and enhance model robustness, we introduce the concept of topological relational inference (TRI) and propose two novel options for information passing which rely on the local topological structure of each node: (i) Inject a new topology-induced multiedge between two nodes based on shape similarity of their local neighborhoods; (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 a 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 on a blind date, based on a careful assessment of interplay among similarities of their interests, socio-demographics as well as that of their close friends, rather than bringing in two individuals together through a 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 as potential churn customer based not only on 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 topology-induced 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 a level of pair-wise connectivity, and such local topological side information in (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 topology-induced 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-theart baselines on 6 out 7 graphs and delivers substantially higher robustness (i.e., up to 10% in performance gains under noisy scenarios) than baselines on all 7 datasets.

heading: 2 Related Work
text: 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 a graph-based convolution in Fourier domain. However, complexity of this model is 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 [30] 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) [31], higher-order graph convolutional architectures (MixHop) [3], multi-scale graph convolution (N-GCN) [2], and Lévy Flights Graph Convolutional Networks (LFGCN) [14]. In addition to random walks, other recent approaches include GNNs on directed graphs (MotifNet) [35], graph convolutional networks with attention mechanism (GAT, SPAGAN) [48, 52], and graph Markov neural network (GMNN) [39]. Most recently, Liu et al. [34] consider utilizing 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 topological signatures include kernel-based methods [46, 40, 33, 55, 32] 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 or removes existing edges. Importantly, PEGN-RC does not integrate topology of both graph and node attributes, while TRI-GNN does.

heading: 3 Preliminaries on Topological Data Analysis and Persistent Homology
text: 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 continuous 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 a discrete sample from some unknown metric spaceM. 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 ofM. 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 G1 ⊆ G2 ⊆ . . . ⊆ Gm = 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 Ci (e.g., a clique complex) induced by Gi. The sequence {Gi} induces a filtration: nested sequence of simplicial complexes C1 ⊆ C2 ⊆ . . . ⊆ Cm = 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 Cbσ at which we first record (i.e., birth) the n-dimensional topological feature σ (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 σ is dσ − bσ. To evaluate all topological features together, we consider a persistence diagram (PD) where the multi-set Dn = {(bσ, dσ) ∈ R2 : dσ > bσ} ∪∆ records the birth and deaths of all n-cycles in the filtration {Ci}. Here, ∆ = {(t, t)|t ∈ 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 ∆ [13].
Depending on the question at 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 : V 7→ N. As degree is an integer valued function, so are our thresholds {αi} ⊂ N. Our sublevel filtration is then defined as follows. Let Vαi = {u ∈ V | f(u) ≤ αi}. Then, Gαi is the subgraph generated by Vαi . In particular, the edge euv ∈ E is in Gαi if both u and v are in Vαi . We call this degree based filtration. In addition, we consider a second filtration defined by the edge-weight function on the graph where edge weights are induced by similarity of node attributes. We call this attribute based filtration (See Section 4). Note that degree based filtration
is induced only by the graph properties, while attribute based filtration is constructed by using the features coming from the observed data.

heading: 4 Topological Relational Inference Graph Neural Network (TRI-GNN)
text: Problem Statement Let G = (V, E) be an attributed graph with a set of nodes V , a set of edges E ⊆ V × V and euv ∈ E denoting an edge between nodes u, v ∈ V . The total number of nodes in G is N = |V|. Let W ∈ RN×N be a N ×N -adjacency matrix of G such that ωuv = 1 for euv ∈ E and 0 otherwise, and D be a diagonal N ×N -degree matrix with Duu = ∑ v ωuv. For undirected graphs W is symmetric (i.e., W = W>). To feed in directed graphs into the graph neural network architecture, we set W ′ = (W>+W )/2. Finally, each u ∈ V is equipped with a set of node features, i.e., Xu = (Xu1, Xu2, . . . , XuF ) represents an F -dimensional feature vector for node u ∈ V , and X is a N ×F -matrix of all node features. Our objective is to develop a robust semi-supervised classifier such that we can predict unknown node labels in G, given some training set of nodes in G with prior labeling information. Figure 1 illustrates our TRI-GNN model framework.

heading: 4.1 Topology-induced Multigraph Representation
text: 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 [35, 47]. Our aim is to systematically extract all n-dimensional 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 Gku = (Vku , Eku) ⊆ G, equipped with an edge-weight function τ induced by similarity of node features in Gku , is called a weighted k-hop neighborhood of node u ∈ V if: (1) for any v ∈ Vku , the shortest path between u and v is at most k; (2) edge-weight function τ : Vku ×Vku 7→ R≥0 is such that for any v, w ∈ Vku with evw ∈ Eku , τvw = ||Xv−Xw||, 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) or other distance appropriate for mixed-type data [20]. If τvw ≡ 1 for any evw ∈ Eku , Gku reduces to a conventional k-hop neighborhood.
Armed with the edge-weight function τ induced by node attributes (see Definition 1) or with a node degree function, we now compute a 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 (Gku is equipped with an edge-weight function τ based on node attributes) and degree based filtration (Gku is an unweighted graph with τ ≡ 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(Gku) and D(Gkv ) be persistence diagrams of the weighted k-hop neighborhood subgraphs Gku and Gkv of nodes u and v, respectively. We measure topological similarity between Gku and Gkv with Wasserstein distance between the corresponding persistence diagrams as dWp(Gku,Gkv ) = infγ (∑ x∈D(Gku)∪∆ ||x − γ(x)||p∞ ) 1 p , where p ≥ 1 and γ is taken over all bijective maps between D(Gku) ∪∆ and D(Gkv ) ∪∆, 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-induced multigraph representation of G, where a multiedge between nodes u and v comprises information on (tangible) connectivity between u and v (i.e, existence of euv) as well as on strong and weak topological similarity of the local neighborhoods of u and v, irregardless whether euv exists.
Definition 3. (Topology-induced Multigraph Representation (TIMR)) Consider a graph G = (V, E), with dW,p(Gku,Gkv ) as a measure of topological similarity among two k-hop neighborhoods
Gku and Gkv , for all u, v ∈ V (see Definition 1). Then a topology-induced multigraph representation of G is defined as Ω = (V, E topo), where E topo is a set of multiedges such that for any u, v ∈ V and thresholds 1, 2 ∈ R+
etopouv = {1euv∈E ,1dW,p(Gku,Gkv )∈[0, 1],−1dW,p(Gku,Gkv )∈[ 2,∞)}. (1)
Note that {dW,p(Gku,Gkv ) ∈ [0, 1]} and {dW,p(Gku,Gkv ) ∈ [ 2,∞)} are incompatible events. Hence, multiedges have multiplicity at most 2 and E topo is a multiset of {(1, 1, 0); (0, 1, 0); (1, 0,−1); (0, 0,−1)}. The intuition behind TIMR is to reflect a level of shape similarity among any two node neighborhoods, irregardless whether there exists an edge between these nodes in G. Later, by using Ω, we induce a graph W topo (Figure 1) defined as follows: If neighborhoods of two nodes in G are topologically similar, we add an edge between the nodes if 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 topology-induced adjacency matrices, W topo + and W topo − , respectively
W topo + uv = [ 0 ≤ dfW,p(G k u,Gkv ) < 1 ] , W topo − uv = [ 2 < d f W,p(G k u,Gkv ) <∞ ] , (2)
where [·] is an Iverson bracket, i.e., 1 whenever a condition in the bracket is satisfied, and 0 otherwise. Selection of hyperparameters 1 and 2 can be performed by assessing quantiles of the empirical distribution of shape similarities and then cross-validation. Thresholds 1 and 2 are used to reinforce meaningful edge structures and suppress noisy edges.
How does TIMR help? TIMR allows us not only to inject a new edge among two nodes if shapes of their multi-hop neighborhoods are sufficiently close, but also to eliminate an existing edge if topological distance among their multi-hop node neighborhoods is higher than predefined threshold 2. 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 a 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 an 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 topology-induced links and to suppress edges induced by the attacker with negative topology-induced links.

heading: 4.2 TIMR Theoretical Stability Guarantees
text: We now establish theoretical stability properties of the TIMR average degree. The average degree is known to be closely related to performance in node classification tasks [28, 17, 1] and, hence, degree-dependent regularization is often used in adversarial training [38, 49, 44]. Here we prove that under perturbations of the observed graph G, average degrees of the TIMR graphs of the original and distorted copies remain close. That is, the proposed TRI framework allows us to increase robustness
of the graph degree properties with respect to graph perturbations and attacks. Given that persistent homology representations are known to 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 dWp between their persistence diagrams as follows. Let u
± be a node in G± and Gku± be k-neighborhood of the u ± in G±. Let
dk(u +, u−) = dW1(D0(Gku+),D0(G k u−)),
where dW1 is Wasserstein-1 distance (see Definition 1), and D0(G) is the persistence diagram of 0-cycles. Let ϕ : V + → V − be a bijection between node sets of G+ and G−, respectively. Then, the local k-distance between G+ and G− is defined as
Dk(G+,G−) = min ϕ ∑ u+ dk(u +, ϕ(u+)).
We now have the following stability result: Theorem 1 (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 1 and 2. Let α± be the average degree of T±. Then, there exists a constant K( 1, 2) > 0 such that
|α+ − α−| ≤ K( 1, 2)Dk(G+,G−).
The proof of the theorem is given in Appendix A in 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 λ2(G) is the second smallest eigenvalue of the graph Laplacian L(G), and it is considered to be a spectral measure to determine the robustness of the graph [45].
Conjecture: Let G be a graph, and let G′ be a graph which is obtained by adding one edge e to G, i.e., G′ = G ∪ e. Let T, T ′ be the TIMR graphs induced by G,G′, respectively. Then,
|λ2(T ′)− λ2(T )| ≤ K( 1, 2)|λ2(G′)− λ2(G)|.
Note that this conjecture is not true for degree based TIMR graphs. The reason for that when one adds an edge euv to G, then this operation significantly changes k-neighborhoods of all nodes in Nk(vi) andNk(vj). Since degree based TIMR construction depends on persistence diagrams of these k-neighborhoods, adding such an edge causes an uncontrollable effect on the algebraic connectivity. However, in attribute based construction, similarity is only based on the attributes, and the distances in the graph does not have an effect on 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 are identical.

heading: 4.3 STAN: learning from Subgraphs, Topology and Attributes of Neighbors
text: 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 at the node-level. However, such higher-order architectures largely focus on global network topology and do not account for the important local graph structures. Also, performance of such higher-order graph convolution architectures tend to suffer from over-smoothing and be susceptible to noisy observations, since their propagation schemes recursively update each node’s feature vector by aggregating over information delivered by all further nodes captured by a random walk.
Here we propose a 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 a form of topological edge weights, (ii) calculates topological average of neighborhood features, (iii) aggregates them with the initial node features.
Let X(0)u = Xu be the initial node features for u ∈ V and T be the number of STAN iterations. Then we iteratively update the feature representation of node u using side information collected from nodes within its k-hop local neighborhood via X(t+1)u = fup ( φaggr ( X (t) u , α(u) ∑ v∈Vk(u) d̂uv · X (t) v )) , where fup is the update function such as a multi-layer perceptron (MLP) and a gated network, φaggr is function that aggregates topological features into node features, such as sum and mean; α(u) is a weighting factor which can be set either as a hyperparameter or a fixed scalar, and d̂uv are normalized topological edge weights
d̂uv = exp
[( dfW,p(Gu,Gv) )−1]∑ v∈Vk(u) exp [( dfW,p(Gu,Gv)
)−1] . The core principle of STAN is to assign different importance scores to nodes, depending on how similar topologically their neighborhoods are to the target node, and to control the impact on the target node prediction when aggregating neighborhoods’ information. For instance, suppose target node is u and we also have nodes v and w. We assign a higher weight to the edge between u and v (if the shapes of their neighborhoods are more similar) and a lower weight to the edge between u and w (if neighborhoods of u and w have more distinct topology). As a result, the updated node features of u will be more affected by v.

heading: 4.4 Convolution based TRI-GNN Layer
text: We now turn to construction of the TRI-GNN layer. Let W ∈ RN×N×3 be a 3-dimension tensor, where N is the number of nodes and 3 is the number of candidate adjacency matrices (i.e., W , W topo + , and W topo −
). Let W uvr be the r-th type of edge between nodes u and v of W , where u ∈ {1, . . . , N}, v ∈ {1, . . . , N}, and r ∈ {1, 2, 3}. That is, we denote W , W topo+ , and W topo− by setting r = 1, 2, 3. We then consider a joint topology-induced adjacency matrix W topo
W topouv =
{ 1, if ∑ rW uvr > 0
0, otherwise . (3)
In the experiments, we utilize the classification function for the generalized semi-supervised learning as the default filter engine of TRI-GNN. Given W topo, we compute topological distance-based graph Laplacian Ltopo = (D̃topo)−σW̃ topo(D̃topo)σ−1, where W̃ topo = (W topo + I)ρ, D̃topo = ∑ v W̃ topo uv , σ ∈ [0, 1], and ρ ∈ (0,∞). Equipped with the new graph Laplacian Ltopo and node information matrix X(T ) at iteration T , TRI-GNN uses the following graph convolution layer
H(`+1) = ψ ( µ ( I − µLtopo )−1 H(`)Θ(`) ) = ψ ( µ ∞∑ i=0 ( µLtopo )i H(`)Θ(`) ) ,
where µ ∈ (0, 1] is a regularization parameter, H(`) ∈ RN×F` and H(`+1) ∈ RN×F`+1 are input and output activations for layer ` (H(0) = X(T )), Θ ∈ RF`×F`+1 are the trainable parameters of
TRI-GNN, and ψ is an element-wise nonlinear activation function such as ReLU. In the experiments µ 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 maxi = dRµe is a suitable rule of thumb (where R ∈ [2, 50]), while the closer σ is to 0, the 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.

heading: 5 Experiments
text: 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.

heading: 5.1 Experimental Settings
text: Datasets We compare TRI-GNN with the state-of-the-art (SOA) baselines, using standard publicly available real and synthetic networks: (1) 3 citation networks [41]: 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, or generator and we use total line charging susceptance (BR_B) as edge weight. For more details see Table I (in Appendix C.1).
Baselines We compare TRI-GNN with 14 SOA GNNs: (i) 5 higher-order graph convolution architectures: LGCNs [22], APPNP [31], VPN [25], LFGCN [14], and MixHop [3]; (ii) 2 graph attention mechanism: GAT [48] and SPAGAN [52]; (iii) 4 GNNs with polynomial filters: ChebNet [18], GCN [30], MotifNet [35], and ARMA [6]; (iv) 2 GNNs by learning the generative distribution: GMNN [39] and RGCN [57]; and (v) 1 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-GNND (node degree as filtration function). In addition, in our robustness experiments, we select the 4 strongest baselines in each of the GNN areas: random walks, graph attention networks, higher-order graph convolutional models, and robust graph convolutional networks (i.e., 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://github.com/TRI-GNN/TRI-GNN.git.

heading: 5.2 Performance on Node Classification
text: Table 1 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
information. The best results are highlighted in bold for all datasets. As Table 1 shows, TRI-GNND and TRI-GNNA outperform all baselines on all 7 but 1 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, we find that for sparser 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 attribute-induced PH, while for denser, more homogeneous graphs as IEEE 118-bus, attribute-based filtration is the key. These insights echo findings in real citation networks.
Ablation Study Our TRI framework contains two key components: (i) encoding higher-order topological information via TIMR, (ii) STAN, i.e., updating the node features by aggregating information from subgraphs, topology, and neighborhood features. To glean a deeper insight into how different components help TRI-GNN to achieve highly competitive results, we conduct experiments by removing individual component separately, namely (1) TRI-GNND w/o TIMR (i.e., denoted by Ω), (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 Table 2 shows, both TIMR Ω and STAN indeed yield significant performance improvements on all datasets. The ablation study on 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.
Boundary Sensitivity We select the 1 and 2 values based on quantiles of Wasserstein distances between persistence diagrams (see Figure 3a). The optimal choice of 1 and 2 can be obtained via cross-validation. For instance, the optimal quantile of 1 and 2 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 2 are 0.1-quantile and 6.74 (maximum), respectively. For 1, we generate a sequence from 0.50 to 2.00 with increment of the sequence 0.05; for 2, we generate a sequence from 2.50 to 6.74 with increment of the sequence 0.5. Based on cross-validation, we conduct experiments in different 1 and 2 combinations. Figures 3b and 3c show the performances with respect to different thresholds ( 1 and 2) combinations (where † denotes the i (where i ∈ {1, 2}) is not fixed). From the results in Figure 3, we find that ( 1, 2) 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 1 and 2 on ACTIVSg500 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 TRIGNNA, and analogous robustness for TRI-GNND 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 fake edges to the number of existing edges varies from 0 to 100%. As Figure 4 shows, TRI-GNNA 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-ML). These findings indicate that TRI-GNNA is again the most robust GNN node classifier under random attacks. By aggregating local
topological information from node features and neighborhood substructures, TRI-GNNA can “absorb” noisy edges and, as a result, exhibits less sensitivity to graph perturbations and adversarial attacks.
Computational Costs In less extreme scenarios, the expected number of nodes in the k-hop neighborhood can be approximated by d̄k, 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 O(M3), where M is the total number of barcodes in the both persistence diagrams. In the worst case scenario, if we use a very fine filtering function for persistence diagrams of k-hop neighborhoods, it would give at most 2d̄k barcodes (i.e., the number of barcodes in each k-hop neighborhood is at most d̄k and we compare two k-hop neighborhoods). Considering we use the degree filtering function for our persistence diagrams, we expect to have much less (∼ d̄k) barcodes in the 0-th persistence diagram of a k-hop neighborhood by using the technique in [29]. Hence, the overall computational complexity would be of stochastic orderO(N2d̄ 3k2 ). It may be costly to run PH for denser graphs (currently, computational complexity is the main roadblock for all PH-based methods on graphs) but as we noted earlier, for denser graphs we may use a degree filtration under lower k-hops which is still found to be very powerful even for small k. 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.

heading: 6 Conclusion
text: We have proposed a novel perspective to node classification with GNN, based on the TDA concepts invoked within each local node neighborhood. The new TRI approach has shown to deliver highly competitive results on clean graphs and substantial improvements in robustness against graph perturbations. In 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 be dominated by the abundant group, such bias is very likely to exist and to be non-negligible. Mitigating it is a 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 a 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).

heading: Acknowledgements
text: This work is 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 N000142112226. Part of 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.

Review summaries:
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. 

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.

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.