Weighted Graph Cuts without Eigenvectors A Multilevel Approach

By Inderjit S. Dhillon, Yuqiang Guan, Brian Kulis. 2007

1,091 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics, Graph Learning, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

In Graph Learning

In Algorithms & Complexity

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.”
Spectral Networks and Locally Connected Networks on Graphs (2013, background): “We assume without loss of generality that the input signal is a real signal deﬁned in Ω 0 , and we denote by f k the number of “ﬁlters” created at each layer k .”
Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “LeNet used 2×2 max-pooling; in ChebNet and MoNet we used three convolutional layers, interleaved with pooling layers based on the Graclus method [14] to coarsen the graph by a factor of four.”
Fast Graph Representation Learning with PyTorch Geometric (2019, methodology): “We currently provide implementation examples for Graclus (Dhillon et al., 2007; Fagginger Auer & Bisseling, 2011) and voxel grid pooling (Simonovsky & Komodakis, 2017), the iterative farthest point sampling algorithm (Qi et al., 2017) followed by 𝑘 -NN or query ball graph generation (Qi et al., 201”
Hierarchical Graph Representation Learning with Differentiable Pooling (2018, methodology): “This is because many collaboration graphs in COLLAB show only single-layer community structures, which can be captured well with pre-computed graph clustering algorithm [9].”
Towards Sparse Hierarchical Graph Classifiers (2018, methodology): “…[28, 1], all earlier works in this area assume a ﬁxed, pre-deﬁned cluster assignment, that is obtained by running a clustering algorithm on the graph nodes, e.g. using the GraClus algorithm [7] to obtain structure-dependent cluster assignments or ﬁnding clusters via k-means on node features [21].”
3D shape segmentation via shape fully convolutional networks (2017, neutral): “The pooling method for graphs [12, 13] coarsens the graph 50 with the Graclus multi-level clustering algorithm [40].”
A Comprehensive Survey on Graph Neural Networks (2019, methodology): “Input graphs are ﬁrst coarsened into multiple levels by the Graclus algorithm [100].”
Community detection in graphs (2009, methodology): “The initial decomposition of the graph is carried out through the multilevel method by Dhillon et al. (Dhillon et al., 2007).”
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…”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “have been proposed for detecting communities in undirected networks that are disjoint [4, 13, 21, 38, 40], overlapping [3, 6, 11,”
Spectral Embedding of Signed Networks (2015, background): “Weighted kernel k-means clustering objective is mathematically equivalent to a general spectral clustering objective [5] and can outperform spectral methods in terms of quality, speed, and memory usage.”
Towards Internet-scale multi-view stereo (2010, methodology): “We use Graclus [5, 16] for Normalized Cuts, PMVS [7] for the core MVS reconstruction , and QSplat [21] for the final visualization.”
Graph Neural Networks: A Review of Methods and Applications (2018, methodology): “Graclus (Dhillon et al., 2007) provides a faster way to cluster nodes and it is applied as a pooling module.”
Robust Spatial Filtering With Graph Convolutional Neural Networks (2017, methodology): “Some also use off-the-shelf software such as Graclus [17].”