Topological Relational Learning on Graphs

Yuzhou Chen, Baris Coskunuzer, Yulia R. Gel

Graph Neural Networks (GNNs) have become the go-to tool for learning from interconnected data. However, standard GNNs primarily rely on immediate pairwise connections (edges) to pass information, which leaves them vulnerable to two major headaches: over-smoothing (where node features become indistinguishable as layers increase) and extreme sensitivity to noise (where a few adversarial or fake edges can easily derail the model).

To address these blind spots, researchers have introduced TRI-GNN, a novel framework that applies a "topological" lens to graph learning. By rewiring graphs based on the persistent homology—or the "shape"—of local node neighborhoods, TRI-GNN integrates higher-order structural summaries to overcome common GNN failures.

The core argument behind TRI-GNN is that traditional GNNs miss out on "higher-order" information. Structural patterns like loops, holes, and clusters exist within a node's extended neighborhood but are often ignored by simple edge-to-edge message passing. By bridging the gap between Topological Data Analysis (TDA) and node-level classification, TRI-GNN captures these complex structural signatures.

Methodology: Topological Relational Inference (TRI)

The proposed framework consists of two main components designed to inject topological awareness into the learning process:

  1. TIMR (Topology-induced Multigraph Representation): Think of this as a structural "matchmaking" service for nodes. Instead of just looking at existing edges, TIMR calculates the Persistent Homology (PH) of a node’s $k$-hop neighborhood. It then compares these topological signatures using the Wasserstein distance.
  2. If two nodes have very similar neighborhood shapes, a positive topology-induced edge is added, even if they weren't originally connected.
  3. If an existing edge connects two nodes with wildly different neighborhood shapes, it is flagged as a negative topology-induced edge and its influence is suppressed.
  4. STAN (Subgraphs, Topology, and Attributes of Neighbors): This is a novel feature propagation scheme. It updates a node's features by weighting its neighbors based on their topological similarity. If a neighbor's "shape" matches the target node's "shape," its information is given more weight during the aggregation step.
TRI-GNN Architecture

The final TRI-GNN layer uses a joint adjacency matrix that combines the original graph structure with these new topological insights, regularized specifically to prevent over-smoothing.

Key Insights

  • Shape as a Robustness Proxy: The "shape" of a neighborhood is much harder to distort with a few random, noisy edges than simple adjacency. This makes topology an excellent "remedial ingredient" against adversarial attacks.
  • Local vs. Global TDA: While previous research often used TDA for whole-graph classification (e.g., predicting molecule toxicity), this paper successfully applies it to node-level tasks by focusing on local $k$-hop filtrations.
  • Theoretical Stability: The authors provide mathematical proof showing that the average degree of their rewired "TIMR" graph remains stable even when the original graph is perturbed, offering a strong theoretical foundation for its robustness.

Experimental Results

The model was evaluated on seven diverse datasets, including standard Citation Networks (Cora-ML, CiteSeer, PubMed) and Synthetic Power Grid Networks (IEEE 118-Bus, ACTIVSg series), where infrastructure robustness is paramount.

Performance Comparison Table
  • Superior Accuracy: As shown in the results, TRI-GNN outperformed 14 state-of-the-art baselines (including GCN, GAT, and APPNP) on 6 out of 7 datasets.
  • Resilience to Attacks: In "random attack" scenarios where fake edges were injected, TRI-GNN showed remarkable stability. On the Cora-ML dataset, it maintained high accuracy even when the number of noise edges equaled the number of original edges, yielding up to a 10% performance gain over the best baselines in high-noise environments.
  • Ablation Success: Removing either the TIMR rewiring or the STAN feature weighting led to a drop in performance, proving that both structural and feature-based topological information are necessary for the model's success.

Limitations and Future Directions

While powerful, the framework does have limitations. Calculating persistent homology and Wasserstein distances for every node neighborhood is computationally expensive, with a complexity of roughly $O(N^2 \bar{d}^{3k/2})$. While manageable for small neighborhood radii ($k$) and sparse graphs, it could become a bottleneck for massive, dense social networks.

Additionally, because the model reinforces connections between "similar" neighborhoods, it might inadvertently amplify homophily or bias in social data, potentially reinforcing "echo chambers."

Looking ahead, the research team plans to explore applying TRI-GNN to structured graph pooling, which could unlock new capabilities in hierarchical graph representation learning.

Summary updated

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.
BibTeX
@inproceedings{chen2021topological,
  author = {Yuzhou Chen and Baris Coskunuzer and Yulia R. Gel},
  title = {{Topological Relational Learning on Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=K_TKk5yN15},
}
Figure