PHLP: Sole Persistent Homology for Link Prediction -- Interpretable Feature Extraction

• URL: http://arxiv.org/abs/2404.15225v1
• Date: Tue, 23 Apr 2024 16:54:56 GMT
• Title: PHLP: Sole Persistent Homology for Link Prediction -- Interpretable Feature Extraction
• Authors: Junwon You, Eunwoo Heo, Jae-Hun Jung,
• Abstract summary: Link prediction (LP) is a significant research area in graph data. Although graph neural network (GNN)-based models have achieved high performance in LP, understanding why they perform well is challenging. We propose a novel method that employs PH for LP (PHLP) focusing on how the presence or absence of target links influences the overall topology.
• Score: 2.8413459430736396
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Link prediction (LP), inferring the connectivity between nodes, is a significant research area in graph data, where a link represents essential information on relationships between nodes. Although graph neural network (GNN)-based models have achieved high performance in LP, understanding why they perform well is challenging because most comprise complex neural networks. We employ persistent homology (PH), a topological data analysis method that helps analyze the topological information of graphs, to explain the reasons for the high performance. We propose a novel method that employs PH for LP (PHLP) focusing on how the presence or absence of target links influences the overall topology. The PHLP utilizes the angle hop subgraph and new node labeling called degree double radius node labeling (Degree DRNL), distinguishing the information of graphs better than DRNL. Using only a classifier, PHLP performs similarly to state-of-the-art (SOTA) models on most benchmark datasets. Incorporating the outputs calculated using PHLP into the existing GNN-based SOTA models improves performance across all benchmark datasets. To the best of our knowledge, PHLP is the first method of applying PH to LP without GNNs. The proposed approach, employing PH while not relying on neural networks, enables the identification of crucial factors for improving performance.

Related papers

• Boosting Graph Pooling with Persistent Homology [8.477383770884508]
  naively plugging PH features into GNN layers always results in marginal improvement with low interpretability. We investigate a novel mechanism for injecting global topological invariance into pooling layers using PH, motivated by the observation that filtration operation in PH naturally aligns graph pooling in a cut-off manner. Experimentally, we apply our mechanism to a collection of graph pooling methods and observe consistent and substantial performance gain over several popular datasets.
  arXiv  Detail & Related papers  (2024-02-26T07:00:24Z)
• Going beyond persistent homology using persistent homology [5.724311218570011]
  We introduce a novel concept of color-separating sets to provide a complete resolution to this important problem. We propose RePHINE for learning topological features on graphs.
  arXiv  Detail & Related papers  (2023-11-10T16:12:35Z)
• GPatcher: A Simple and Adaptive MLP Model for Alleviating Graph Heterophily [15.93465948768545]
  We demystify the impact of graph heterophily on graph neural networks (GNNs) filters. We propose a simple yet powerful GNN named GPatcher by leveraging the patch-Mixer architectures. Our model demonstrates outstanding performance on node classification compared with popular homophily GNNs and state-of-the-art heterophily GNNs.
  arXiv  Detail & Related papers  (2023-06-25T20:57:35Z)
• Energy-based Out-of-Distribution Detection for Graph Neural Networks [76.0242218180483]
  We propose a simple, powerful and efficient OOD detection model for GNN-based learning on graphs, which we call GNNSafe. GNNSafe achieves up to $17.0%$ AUROC improvement over state-of-the-arts and it could serve as simple yet strong baselines in such an under-developed area.
  arXiv  Detail & Related papers  (2023-02-06T16:38:43Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Cyclic Label Propagation for Graph Semi-supervised Learning [52.102251202186025]
  We introduce a novel framework for graph semi-supervised learning called CycProp. CycProp integrates GNNs into the process of label propagation in a cyclic and mutually reinforcing manner. In particular, our proposed CycProp updates the node embeddings learned by GNN module with the augmented information by label propagation.
  arXiv  Detail & Related papers  (2020-11-24T02:55:40Z)
• Data-Driven Learning of Geometric Scattering Networks [74.3283600072357]
  We propose a new graph neural network (GNN) module based on relaxations of recently proposed geometric scattering transforms. Our learnable geometric scattering (LEGS) module enables adaptive tuning of the wavelets to encourage band-pass features to emerge in learned representations.
  arXiv  Detail & Related papers  (2020-10-06T01:20:27Z)
• Adaptive Universal Generalized PageRank Graph Neural Network [36.850433364139924]
  Graph neural networks (GNNs) are designed to exploit both sources of evidence but they do not optimally trade-off their utility. We introduce a new Generalized PageRank (GPR) GNN architecture that adaptively learns the GPR weights. GPR-GNN offers significant performance improvement compared to existing techniques on both synthetic and benchmark data.
  arXiv  Detail & Related papers  (2020-06-14T19:27:39Z)
• Unifying Graph Convolutional Neural Networks and Label Propagation [73.82013612939507]
  We study the relationship between LPA and GCN in terms of two aspects: feature/label smoothing and feature/label influence. Based on our theoretical analysis, we propose an end-to-end model that unifies GCN and LPA for node classification. Our model can also be seen as learning attention weights based on node labels, which is more task-oriented than existing feature-based attention models.
  arXiv  Detail & Related papers  (2020-02-17T03:23:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.