Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach

• URL: http://arxiv.org/abs/2102.03609v1
• Date: Sat, 6 Feb 2021 16:49:02 GMT
• Title: Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• Authors: Manohar Kaul and Masaaki Imaizumi
• Abstract summary: higher-order structure prediction methods are mostly based on feature extraction procedures, which work well in practice but lack theoretical guarantees. We develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process. Our method substantially outperforms several baseline higher-order prediction methods.
• Score: 22.818503693119315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dynamic graphs are rife with higher-order interactions, such as co-authorship relationships and protein-protein interactions in biological networks, that naturally arise between more than two nodes at once. In spite of the ubiquitous presence of such higher-order interactions, limited attention has been paid to the higher-order counterpart of the popular pairwise link prediction problem. Existing higher-order structure prediction methods are mostly based on heuristic feature extraction procedures, which work well in practice but lack theoretical guarantees. Such heuristics are primarily focused on predicting links in a static snapshot of the graph. Moreover, these heuristic-based methods fail to effectively utilize and benefit from the knowledge of latent substructures already present within the higher-order structures. In this paper, we overcome these obstacles by capturing higher-order interactions succinctly as \textit{simplices}, model their neighborhood by face-vectors, and develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process (i.e., a sequence of graph snapshots). Our method substantially outperforms several baseline higher-order prediction methods. As a theoretical achievement, we prove the consistency and asymptotic normality in terms of the Wasserstein distance of our estimator using Stein's method.

Related papers

• SPHINX: Structural Prediction using Hypergraph Inference Network [19.853413818941608]
  We introduce Structural Prediction using Hypergraph Inference Network (SPHINX), a model that learns to infer a latent hypergraph structure in an unsupervised way. We show that the recent advancement in k-subset sampling represents a suitable tool for producing discrete hypergraph structures. The resulting model can generate the higher-order structure necessary for any modern hypergraph neural network.
  arXiv  Detail & Related papers  (2024-10-04T07:49:57Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• Beyond spectral gap (extended): The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. Current theory does not explain that collaboration enables larger learning rates than training alone. This paper aims to paint an accurate picture of sparsely-connected distributed optimization.
  arXiv  Detail & Related papers  (2023-01-05T16:53:38Z)
• Learning the Evolutionary and Multi-scale Graph Structure for Multivariate Time Series Forecasting [50.901984244738806]
  We show how to model the evolutionary and multi-scale interactions of time series. In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations. A unified neural network is provided to integrate the components above to get the final prediction.
  arXiv  Detail & Related papers  (2022-06-28T08:11:12Z)
• 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)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Convergent Boosted Smoothing for Modeling Graph Data with Tabular Node Features [46.052312251801]
  We propose a framework for iterating boosting with graph propagation steps. Our approach is anchored in a principled meta loss function. Across a variety of non-iid graph datasets, our method achieves comparable or superior performance.
  arXiv  Detail & Related papers  (2021-10-26T04:53:12Z)
• Link Prediction on N-ary Relational Facts: A Graph-based Approach [18.01071110085996]
  Link prediction on knowledge graphs (KGs) is a key research topic. This paper considers link prediction upon n-ary relational facts and proposes a graph-based approach to this task.
  arXiv  Detail & Related papers  (2021-05-18T12:40:35Z)
• A Generalized Weisfeiler-Lehman Graph Kernel [2.959278299317192]
  Weisfeiler-Lehman graph kernels are among the most prevalent graph kernels due to their remarkable time complexity and predictive performance. We propose a generalization of Weisfeiler-Lehman graph kernels which takes into account the similarity between trees rather than equality.
  arXiv  Detail & Related papers  (2021-01-20T13:03:51Z)
• Neuralizing Efficient Higher-order Belief Propagation [19.436520792345064]
  We propose to combine approaches to learn better node and graph representations. We derive an efficient approximate sum-product loopy belief propagation inference algorithm for higher-order PGMs. Our model indeed captures higher-order information, substantially outperforming state-of-the-art $k$-order graph neural networks in molecular datasets.
  arXiv  Detail & Related papers  (2020-10-19T07:51:31Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.