A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs

By George Karypis, Vipin Kumar. 1998

Subfields: Graph Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Graph Learning

In Optimization & Training

Citations in the corpus

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “And the last step is the graph pooling operation that trades spatial resolution for higher filter resolution.”
Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks (2019, methodology): “sier to implement than the neighborhood search procedure used in previous SGD-based training methods. We use graph clustering algorithms to partition the graph. Graph clustering methods such as Metis [8] and Graclus [4] aim to construct the partitions over the vertices in the graph such that withinc”
Learning Deep Representations for Graph Clustering (2014, background): “Among many existing graph clustering algorithms (Karypis and Kumar 1998)(Shi and Malik 2000) (Van Dongen 2000) (Dhillon, Guan, and Kulis 2007)(Satuluri and Parthasarathy 2009), spectral clustering has attracted people’s great attention in the past decades due to its solid theoretical foundation and ”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “It ﬁrst adopts a graph partitioning algorithm (e.g., METIS [78]) to group nodes into d communities ( d is a user-speciﬁed number).”
Localized matrix factorization for recommendation based on matrix block diagonal forms (2013, methodology): “The time complexity of Node-based bisection in Metis is O(n), where n is the number of non-zeros in a matrix [14].”
Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization (2018, methodology): “In order to construct instances for the decision problem, we partitioned the complete graph into 27 instances, each with 100 nodes, us-ing metis (Karypis and Kumar 1998).”
Bayesian reasoning and machine learning (2012, unknown): “16b), for which a typical criterion is that each subgraph should be roughly of the same size and that there are few connections between the subgraphs[156].”
Experimental validation of a phase-field model for fracture (2017, methodology): “This code was written on a parallel framework using Message Passing Interface library (MPI), Metis library (Karypis and Kumar 1999) for mesh partition and Petsc (Balay et al.”
Building Rome in a day (2009, methodology): “Using MeTiS [7], this graph is partitioned into as many pieces as there are compute nodes.”
Nodal discontinuous Galerkin methods on graphics processors (2009, unknown): “A natural ﬁrst idea is to use conventional graph partitioning software (e.g. [14]).”
The little engine(s) that could: scaling online social networks (2010, methodology): “Graph Partitioning: There exist several offline algorithms for partitioning a graph into a fixed number of equal sized partitions in such a way that the number of inter-partition edges are minimized [10, 19].”
Open-source MATLAB implementation of consistent discretisations on complex grids (2012, methodology): “These cells are subsequently partitioned into a coarse grid by means of the well-known software package METIS [18].”
Ultra-Scalable Spectral Clustering and Ensemble Clustering (2019, methodology): “and Brodley [22] built a bipartite graph structure by treating both base clusters and data objects as graph nodes, and then partitioned the graph via the METIS algorithm [23].”
From "Think Like a Vertex" to "Think Like a Graph" (2013, methodology): “Prominent examples of graph aggregation are graph summarization [22], graph sparsiﬁcation [19], and graph coarsening [12, 11].”