Qiyuan Pang

Qiyuan Pang, Haizhao Yang

We develop a distributed Block Chebyshev-Davidson algorithm to solve large-scale leading eigenvalue problems for spectral analysis in spectral clustering. First, the efficiency of the Chebyshev-Davidson algorithm relies on the prior knowledge of the eigenvalue spectrum, which could be expensive to estimate. This issue can be lessened by the analytic spectrum estimation of the Laplacian or normalized Laplacian matrices in spectral clustering, making the proposed algorithm very efficient for spectral clustering. Second, to make the proposed algorithm capable of analyzing big data, a distributed and parallel version has been developed with attractive scalability. The speedup by parallel computing is approximately equivalent to $\sqrt{p}$, where $p$ denotes the number of processes. {Numerical results will be provided to demonstrate its efficiency in spectral clustering and scalability advantage over existing eigensolvers used for spectral clustering in parallel computing environments.}

Qiyuan Pang, Haizhao Yang

While orthogonalization exists in current dimensionality reduction methods in spectral clustering on undirected graphs, it does not scale in parallel computing environments. We propose four orthogonalization-free methods for spectral clustering. Our methods optimize one of two objective functions with no spurious local minima. In theory, two methods converge to features isomorphic to the eigenvectors corresponding to the smallest eigenvalues of the symmetric normalized Laplacian. The other two converge to features isomorphic to weighted eigenvectors weighting by the square roots of eigenvalues. We provide numerical evidence on the synthetic graphs from the IEEE HPEC Graph Challenge to demonstrate the effectiveness of the orthogonalization-free methods. Numerical results on the streaming graphs show that the orthogonalization-free methods are competitive in the streaming graph scenario since they can take full advantage of the computed features of previous graphs and converge fast. Our methods are also more scalable in parallel computing environments because orthogonalization is unnecessary. Numerical results are provided to demonstrate the scalability of our methods. Consequently, our methods have advantages over other dimensionality reduction methods when handling spectral clustering for large streaming graphs.

Jiawei Xue, Nan Jiang, Senwei Liang et al.

Quantifying the topological similarities of different parts of urban road networks (URNs) enables us to understand the urban growth patterns. While conventional statistics provide useful information about characteristics of either a single node's direct neighbors or the entire network, such metrics fail to measure the similarities of subnetworks considering local indirect neighborhood relationships. In this study, we propose a graph-based machine-learning method to quantify the spatial homogeneity of subnetworks. We apply the method to 11,790 urban road networks across 30 cities worldwide to measure the spatial homogeneity of road networks within each city and across different cities. We find that intra-city spatial homogeneity is highly associated with socioeconomic statuses such as GDP and population growth. Moreover, inter-city spatial homogeneity obtained by transferring the model across different cities, reveals the inter-city similarity of urban network structures originating in Europe, passed on to cities in the US and Asia. Socioeconomic development and inter-city similarity revealed using our method can be leveraged to understand and transfer insights across cities. It also enables us to address urban policy challenges including network planning in rapidly urbanizing areas and combating regional inequality.

Qiyuan Pang, Kenneth L. Ho, Haizhao Yang

This paper introduces a "kernel-independent" interpolative decomposition butterfly factorization (IDBF) as a data-sparse approximation for matrices that satisfy a complementary low-rank property. The IDBF can be constructed in $O(N\log N)$ operations for an $N\times N$ matrix via hierarchical interpolative decompositions (IDs), if matrix entries can be sampled individually and each sample takes $O(1)$ operations. The resulting factorization is a product of $O(\log N)$ sparse matrices, each with $O(N)$ non-zero entries. Hence, it can be applied to a vector rapidly in $O(N\log N)$ operations. IDBF is a general framework for nearly optimal fast matvec useful in a wide range of applications, e.g., special function transformation, Fourier integral operators, high-frequency wave computation. Numerical results are provided to demonstrate the effectiveness of the butterfly factorization and its construction algorithms.