Hypergraph Partitioning using Tensor Eigenvalue Decomposition

• URL: http://arxiv.org/abs/2011.07683v1
• Date: Mon, 16 Nov 2020 01:55:43 GMT
• Title: Hypergraph Partitioning using Tensor Eigenvalue Decomposition
• Authors: Deepak Maurya and Balaraman Ravindran
• Abstract summary: We propose a novel approach for the partitioning of k-uniform hypergraphs. Most of the existing methods work by reducing the hypergraph to a graph followed by applying standard graph partitioning algorithms. We overcome this issue by utilizing the tensor-based representation of hypergraphs.
• Score: 19.01626581411011
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, we propose a novel approach for the partitioning of k-uniform hypergraphs. Most of the existing methods work by reducing the hypergraph to a graph followed by applying standard graph partitioning algorithms. The reduction step restricts the algorithms to capturing only some weighted pairwise interactions and hence loses essential information about the original hypergraph. We overcome this issue by utilizing the tensor-based representation of hypergraphs, which enables us to capture actual super-dyadic interactions. We prove that the hypergraph to graph reduction is a special case of tensor contraction. We extend the notion of minimum ratio-cut and normalized-cut from graphs to hypergraphs and show the relaxed optimization problem is equivalent to tensor eigenvalue decomposition. This novel formulation also enables us to capture different ways of cutting a hyperedge, unlike the existing reduction approaches. We propose a hypergraph partitioning algorithm inspired from spectral graph theory that can accommodate this notion of hyperedge cuts. We also derive a tighter upper bound on the minimum positive eigenvalue of even-order hypergraph Laplacian tensor in terms of its conductance, which is utilized in the partitioning algorithm to approximate the normalized cut. The efficacy of the proposed method is demonstrated numerically on simple hypergraphs. We also show improvement for the min-cut solution on 2-uniform hypergraphs (graphs) over the standard spectral partitioning algorithm.

Related papers

• Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking [0.25322020135765466]
  Higher-order link prediction is the task of predicting the existence of a missing hyperedge in a hypergraph. A hyperedge representation learned for higher order link prediction is fully expressive when it does not lose distinguishing power up to an isomorphism. We devise a preprocessing algorithm that can identify certain regular subhypergraphs exhibiting symmetry.
  arXiv  Detail & Related papers  (2024-02-17T17:13:41Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• Tensorized Hypergraph Neural Networks [69.65385474777031]
  We propose a novel adjacency-tensor-based textbfTensorized textbfHypergraph textbfNeural textbfNetwork (THNN) THNN is faithful hypergraph modeling framework through high-order outer product feature passing message. Results from experiments on two widely used hypergraph datasets for 3-D visual object classification show the model's promising performance.
  arXiv  Detail & Related papers  (2023-06-05T03:26:06Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• Hypergraph Convolutional Networks via Equivalency between Hypergraphs and Undirected Graphs [59.71134113268709]
  We present General Hypergraph Spectral Convolution(GHSC), a general learning framework that can handle EDVW and EIVW hypergraphs. In this paper, we show that the proposed framework can achieve state-of-the-art performance. Experiments from various domains including social network analysis, visual objective classification, protein learning demonstrate that the proposed framework can achieve state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-03-31T10:46:47Z)
• Love tHy Neighbour: Remeasuring Local Structural Node Similarity in Hypergraph-Derived Networks [2.246222223318928]
  We propose a multitude of hypergraph-oriented similarity scores between node-pairs. We provide theoretical formulations to extend graph-topology based scores to hypergraphs.
  arXiv  Detail & Related papers  (2021-10-30T14:12:58Z)
• HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering [9.438207505148947]
  We propose an efficient spectral hypergraph coarsening scheme (HyperSF) for preserving the original spectral (structural) properties of hypergraphs. Our results show that the proposed hypergraph coarsening algorithm can significantly improve the multi-way conductance of hypergraph clustering.
  arXiv  Detail & Related papers  (2021-08-17T22:20:23Z)
• Hypergraph Dissimilarity Measures [8.890638003061605]
  We present measures that assess hypergraph dissimilarity at a specific scale or provide a more holistic multi-scale comparison. We test these measures on synthetic hypergraphs and apply them to biological datasets.
  arXiv  Detail & Related papers  (2021-06-15T15:10:24Z)
• Hyperedge Prediction using Tensor Eigenvalue Decomposition [21.673771194165276]
  Link prediction in graphs is studied by modeling the dyadic interactions among two nodes. Such interactions can be modeled using a hypergraph, which is a generalization of a graph where a hyperedge can connect more than two nodes. We utilize the tensor-based representation of hypergraphs and propose a novel interpretation of the tensor eigenvectors.
  arXiv  Detail & Related papers  (2021-02-06T01:55:04Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

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.