Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning
Jaesun Shin [email protected], Eunjoo Jeon [email protected], Taewon Cho [email protected], Namkyeong Cho [email protected], Youngjune Gwon [email protected] · 2024
Read Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning by Jaesun Shin [email protected], Eunjoo Jeon [email protected], Taewon Cho [email protected], Namkyeong Cho [email protected], Youngjune Gwon [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17468.txt.
Introduction
Jaesun Shin and co-authors give graph neural networks a better sense of shape. Standard message-passing networks embed nodes well but can miss a graph's topology, its holes and loops. Earlier fixes filtered a graph node by node into persistence diagrams, yet lost the node information in the process. The team instead filters by edges and defines a diagram, called TED, that they prove keeps node information while adding topological detail.
Their practical method, LGVR, converts a graph into its line graph, where edges become nodes, and builds the diagram there. Two wrapper frameworks let any message-passing network use it, and the authors prove both beat the classic Weisfeiler-Lehman colouring test in distinguishing power. On graph classification and regression benchmarks, the wrapped models outperformed their plain counterparts.
Catalog record
| CREATOR | Jaesun Shin [email protected], Eunjoo Jeon [email protected], Taewon Cho [email protected], Namkyeong Cho [email protected], Youngjune Gwon [email protected] |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-17468
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning Jaesun Shin [email protected], Eunjoo Jeon [email protected], Taewon Cho [email protected], Namkyeong Cho [email protected], Youngjune Gwon [email protected] Abstract While message passing graph neural networks result in informative node embeddings, they may suffer from describing the topological properties of graphs. To this end, node filtration has been widely used as an attempt to obtain the topological information of a graph using persistence diagrams. However, these attempts have faced the problem of losing node embedding information, which in turn prevents them from providing a more expressive graph representation. To tackle this issue, we shift our focus to edge filtration and introduce a novel edge filtration-based persistence diagram, named Topological Edge Diagram (TED), which is mathematically proven to preserve node embedding information as well as contain additional topological information. To implement TED, we propose a neural network based algorithm, named Line Graph Vietoris-Rips (LGVR) Persistence Diagram, that extracts edge information by transforming a graph into its line graph. Through LGVR, we propose two model frameworks that can be applied to any message passing GNNs, and prove that they are strictly more powerful than Weisfeiler-Lehman type colorings. Finally we empirically validate superior performance of our models on several graph classification and regression benchmarks. Jaesun Shin, Eunjoo Jeon, Taewon Cho, Namkyeong Cho, Youngjune Gwon † † heading: 25 2024 1- 12/23; Revised 1/24 12/24 23-1610 † † shortheadings: LGVR Persistence Diagram / Shin, Jeon, Cho, Cho, and Gwon † † firstpage: 1 † † editor: Sayan Mukherjee keywords Graph Neural Network, Persistence Diagram, Topological Data Analysis, Weisfeiler-Lehman Test, Vietoris-Rips Filtration 1 Introduction Recently, message passing graph neural networks and its variants have emerged as an effective method to learn graph representations ( Morris et al. (2019) ; Chen et al. (2019) ; Balcilar et al. (2020) ; Kondor et al. (2018) ; Cai et al. (2021) ; Hamilton et al. (2017) ; Gilmer et al. (2017) ; Wu et al. (2020) ). Since message passing GNNs are designed to learn node representations, they can extract informative node embeddings by capturing localized information. However, they can hardly capture topological information of the entire graph ( Chen et al. (2020) ; Hofer et al. (2020) ; Balcilar et al. (2021) ). In this vein, various topological methods have been proposed ( Zhang et al. (2018) ; Ying et al. (2018) ; Ranjan et al. (2020) ; Bouritsas et al. (2020) ). In particular, node filtration has been widely used to extract topological information of graphs using persistence diagrams ( Oudot (2017) ), showing superior performance on graph benchmarks ( Hofer et al. (2020) ; Horn et al. (2021) ; Hofer et al. (2017) ; Carriere et al. (2019) ; Rieck et al. (2019) ; Zhao and Wang (2019) ). For example, Hofer et al. (2020) extracted topological information from the persistence diagram of sublevel sets of a node filtration map over node features. Moreover, Horn et al. (2021) proposed a multi-scale version of Hofer et al. (2020) using k node filtration maps. Theoretically, they claim that persistence diagrams based on node filtration map f_{N} can provide stronger expressivity than the Weisfeiler-Lehman (WL) test ( Weisfeiler and Lehman (1968) ), assuming that the input node features of f_{N} are all different for each node ( Horn et al., 2021 , Theorem 1, 2) . However, even the WL test, which is known to be at least as powerful as message passing GNNs ( Xu et al. (2018a) ), cannot assign different features to different nodes. Furthermore, in cases where this assumption does not hold, there exist graphs that cannot be distinguished by node filtration-based persistence diagrams but can be distinguished by the WL test (Figure 1 ). In other words, node filtration-based persistence diagram cannot provide more powerful GNNs than the WL test in general. Figure 1 : An overview of node filtration and edge filtration of WL coloring. For graphs G and H distinguishable by WL test, the edge filtration-based persistence diagram can also distinguish them while the node filtration-based one cannot. We found out that such topological methods suffer from a loss of coloring information, due to the nature of node filtration, which extracts induced subgraphs (Figure 2 ). To address this, we shift our attention to edges. If we can capture information of two nodes in a single edge, we can extract more fruitful information from edge filtration by directly controlling the connectivity of graphs through edges while including all the node information. With this goal in mind, we propose a novel edge filtration-based persistence diagram, Topologcial Edge Diagram (TED) , which, to the best of our knowledge, is the first approach using edge-based filtration in topological graph representation learning. Specifically, TED is defined as a persistence diagram of Vietoris-Rips filtration ( Hatcher (2002) ; Oudot (2017) ), which is the well-known algebraic topological reconstruction technique, whose a set of graph nodes is represented as a point cloud and edge information as distances between points. In contrast to node filtration, we prove that TED can preserve the expressive power of an arbitrary node coloring (Lemma 8 ). We further prove that TED can even increase the expressive powers of WL colorings thanks to its additional topological information (Theorem 9 ). Next, we propose a novel neural-network-based algorithm, called Line Graph Vietoris-Rips (LGVR) Persistence Diagram , to implement our theoretical foundation. A key challenge is to assign unique features to edges that consist of different node features. To tackle this problem, we construct a map t_{\phi} (Section 5.1 ) that transforms a colored graph into a colored line graph (Definition 11 ) through a neural network, which ensures the uniqueness of edge features. Thanks to this, we prove that LGVR has the same expressivity as TED and further analyze its theoretical expressivity. Through LGVR, we propose two types of topological model frameworks, \mathcal{C} -LGVR and \mathcal{C} -LVGR + , that can be applied to any message passing GNNs \mathcal{C} (Section 6.2 ). From a theoretical perspective, we analyze their theoretical expressivity when \mathcal{C} is either GIN ( Xu et al. (2018a) ) or PPGN ( Maron et al. (2019) ), and prove that our models are strictly more powerful than \mathcal{C} (Corollary 18 ). In addition to proposing a theoretical framework, we performed experiments on several real-world datasets, including 7 classification and 12 regression tasks related to bioinformatics, social networks, and chemical compounds, to substantiate the superiority of our topological models (Section 7 ). We focus on three aspects. First, we test whether our models, \mathcal{C} -LGVR and \mathcal{C} -LVGR + , which theoretically have more powerful representational power than the message passing GNN \mathcal{C} , also show better performances empirically. Our findings demonstrate that our topological models outperform the \mathcal{C} by effectively comprehending diverse graph structures (Table 1 , 3 and 4 ). Next, we conducted comparative experiments for our edge filtration-based methodology and the existing node filtration-based approach ( Xu et al. (2018a) ) to experimentally evaluate the representational capabilities between topological methodologies. In this vein, we compare their performances on both classification and regression tasks, and found that our approach shows superior performance compared to node filtration-based approach, which validates the superiority of edge filtration-based