More Like this

1. Persistence enhanced Graph Neural Network

   Zhao, Qi; Ye, Ze; Chen, Chao; Wang, Yusu (August 2020, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS))

   Local structural information can increase the adaptability of graph convolutional networks to large graphs with heterogeneous topology. Existing methods only use relatively simplistic topological information, such as node degrees.We present a novel approach leveraging advanced topological information, i.e., persistent homology, which measures the information flow efficiency at different parts of the graph. To fully exploit such structural information in real world graphs, we propose a new network architecture which learns to use persistent homology information to reweight messages passed between graph nodes during convolution. For node classification tasks, our network outperforms existing ones on a broad spectrum of graph benchmarks. 

   more » « less
2. Topological Pooling on Graphs

   https://doi.org/10.1609/aaai.v37i6.25866  

   Chen, Yuzhou; Gel, Yulia R. (June 2023, Proceedings of the AAAI Conference on Artificial Intelligence)

   Graph neural networks (GNNs) have demonstrated a significant success in various graph learning tasks, from graph classification to anomaly detection. There recently has emerged a number of approaches adopting a graph pooling operation within GNNs, with a goal to preserve graph attributive and structural features during the graph representation learning. However, most existing graph pooling operations suffer from the limitations of relying on node-wise neighbor weighting and embedding, which leads to insufficient encoding of rich topological structures and node attributes exhibited by real-world networks. By invoking the machinery of persistent homology and the concept of landmarks, we propose a novel topological pooling layer and witness complex-based topological embedding mechanism that allow us to systematically integrate hidden topological information at both local and global levels. Specifically, we design new learnable local and global topological representations Wit-TopoPool which allow us to simultaneously extract rich discriminative topological information from graphs. Experiments on 11 diverse benchmark datasets against 18 baseline models in conjunction with graph classification tasks indicate that Wit-TopoPool significantly outperforms all competitors across all datasets. 

   more » « less
3. Fast and Scalable Complex Network Descriptor Using PageRank and Persistent Homology

   https://doi.org/10.1109/IDSTA50958.2020.9264141  

   Hajij, Mustafa; Munch, Elizabeth; Rosen, Paul (October 2020, 2020 International Conference on Intelligent Data Science Technologies and Applications (IDSTA))

   null (Ed.)

   The PageRank of a graph is a scalar function defined on the node set of the graph which encodes nodes centrality information of the graph. In this article we use the PageRank function along with persistent homology to obtain a scalable graph descriptor and utilize it to compare the similarities between graphs. For a given graph G(V, E), our descriptor can be computed in O(|E|α(|V|)), where a is the inverse Ackermann function which makes it scalable and computable on massive graphs. We show the effectiveness of our method by utilizing it on multiple shape mesh datasets. 

   more » « less
4. Topological data analysis of human brain networks through order statistics

   https://doi.org/10.1371/journal.pone.0276419  

   Das, Soumya; Anand, D. Vijay; Chung, Moo K. (March 2023, PLOS ONE)

   Topaz, Chad M. (Ed.)

   Understanding the common topological characteristics of the human brain network across a population is central to understanding brain functions. The abstraction of human connectome as a graph has been pivotal in gaining insights on the topological properties of the brain network. The development of group-level statistical inference procedures in brain graphs while accounting for the heterogeneity and randomness still remains a difficult task. In this study, we develop a robust statistical framework based on persistent homology using theorder statisticsfor analyzing brain networks. The use of order statistics greatly simplifies the computation of the persistent barcodes. We validate the proposed methods using comprehensive simulation studies and subsequently apply to the resting-state functional magnetic resonance images. We found a statistically significanttopologicaldifference between the male and female brain networks. 

   more » « less
5. Marginal Nodes Matter: Towards Structure Fairness in Graphs

   https://doi.org/10.1145/3655103.3655105  

   Han, Xiaotian; Zhou, Kaixiong; Wang, Ting-Hsiang; Li, Jundong; Wang, Fei; Zou, Na (March 2024, ACM SIGKDD Explorations Newsletter)

   In social network, a person located at the periphery region (marginal node) is likely to be treated unfairly when compared with the persons at the center. While existing fairness works on graphs mainly focus on protecting sensitive attributes (e.g., age and gender), the fairness incurred by the graph structure should also be given attention. On the other hand, the information aggregation mechanism of graph neural networks amplifies such structure unfairness, as marginal nodes are often far away from other nodes. In this paper, we focus on novel fairness incurred by the graph structure on graph neural networks, named structure fairness. Specifically, we first analyzed multiple graphs and observed that marginal nodes in graphs have a worse performance of downstream tasks than others in graph neural networks. Motivated by the observation, we propose Structural Fair Graph Neural Network (SFairGNN), which combines neighborhood expansion based structure debiasing with hop-aware attentive information aggregation to achieve structure fairness. Our experiments show SFairGNN can significantly improve structure fairness while maintaining overall performance in the downstream tasks. 

   more » « less