Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges

• URL: http://arxiv.org/abs/2502.13000v1
• Date: Tue, 18 Feb 2025 16:20:50 GMT
• Title: Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
• Authors: Alex Crane, Thomas Stanley, Blair D. Sullivan, Nate Veldt,
• Abstract summary: We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges. We provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate.
• Score: 8.499685241219366
• License:
• Abstract: We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions they participate in. One well-studied objective is to color nodes to minimize the number of unsatisfied hyperedges -- those containing one or more nodes whose color does not match the hyperedge color. We motivate and present advances for several directions that extend beyond this minimization problem. We first provide new algorithms for maximizing satisfied edges, which is the same at optimality but is much more challenging to approximate, with all prior work restricted to graphs. We develop the first approximation algorithm for hypergraphs, and then refine it to improve the best-known approximation factor for graphs. We then introduce new objective functions that incorporate notions of balance and fairness, and provide new hardness results, approximations, and fixed-parameter tractability results.

Related papers

• Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
  Unsupervised graph alignment finds the one-to-one node correspondence between a pair of attributed graphs by only exploiting graph structure and node features. We propose a principled approach to combine their advantages motivated by theoretical analysis of model expressiveness. We are the first to guarantee the one-to-one matching constraint by reducing the problem to maximum weight matching.
  arXiv  Detail & Related papers  (2024-06-19T04:57:35Z)
• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  Cluster deletion is an NP-hard graph clustering objective with applications in computational and social network analysis. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. We show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a maximum degree in an auxiliary graph and forming a cluster around it.
  arXiv  Detail & Related papers  (2024-04-24T18:39:18Z)
• Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling [6.599344783327054]
  Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation algorithms for an NP-hard parameterized clustering framework called LambdaCC.
  arXiv  Detail & Related papers  (2023-06-08T02:29:37Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. We propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments.
  arXiv  Detail & Related papers  (2022-09-19T14:37:35Z)
• Learning Based Proximity Matrix Factorization for Node Embedding [33.18041180501025]
  Recent progress on node embedding shows that proximity matrix factorization methods gain superb performance and scale to large graphs with millions of nodes. We propose em Lemane, a framework with trainable proximity measures, which can be learned to best suit the datasets and tasks at hand automatically. Our proposed solution outperforms existing solutions on both link prediction and node classification tasks on almost all datasets.
  arXiv  Detail & Related papers  (2021-06-10T03:29:15Z)
• Learning to Estimate Hidden Motions with Global Motion Aggregation [71.12650817490318]
  Occlusions pose a significant challenge to optical flow algorithms that rely on local evidences. We introduce a global motion aggregation module to find long-range dependencies between pixels in the first image. We demonstrate that the optical flow estimates in the occluded regions can be significantly improved without damaging the performance in non-occluded regions.
  arXiv  Detail & Related papers  (2021-04-06T10:32:03Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  multilayer graph clustering aims at dividing the graph nodes into categories or communities. We propose a clustering-friendly embedding of the layers of a given multilayer graph. Experiments show that our method leads to a significant improvement.
  arXiv  Detail & Related papers  (2021-03-30T17:36:40Z)
• 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)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement [55.2456981313287]
  We propose a new disentanglement enhancement framework for deep generative models for attributed graphs. A novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images.
  arXiv  Detail & Related papers  (2020-06-09T16:33:49Z)

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.