David F. Gleich

David F. Gleich

Auto-generated profile, based on publicly available information

David F. Gleich

Purdue University, West Lafayette, USA

Research Focus & Metrics

Academic Career Length

18Years (2009-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
4 August 2017
Verified
Conference Paper
Open access
HYHao Yin
Hao Yin
ABAustin R. Benson
Austin R. Benson
JLJure Leskovec
Jure Leskovec
DGDavid F. Gleich
David F. Gleich
Local graph clustering methods aim to find a cluster of nodes by exploring a small region of the graph. These methods are attractive because they enable targeted clustering around a given seed node and are faster than traditional global graph clustering methods because their runtime does not depend on the size of the input graph. However, current local graph partitioning methods are not designed to account for the higher-order structures crucial to the network, nor can they effectively handle directed networks. Here we introduce a new class of local graph clustering methods that address these issues by incorporating higher-order network information captured by small subgraphs, also called network motifs. We develop the Motif-based Approximate Personalized PageRank (MAPPR) algorithm that finds clusters containing a seed node with minimal \emph{motif conductance}, a generalization of the conductance metric for network motifs. We generalize existing theory to prove the fast running time (independent of the size of the graph) and obtain theoretical guarantees on the cluster quality (in terms of motif conductance). We also develop a theory of node neighborhoods for finding sets that have small motif conductance, and apply these results to the case of finding good seed nodes to use as input to the MAPPR algorithm. Experimental validation on community detection tasks in both synthetic and real-world networks, shows that our new framework MAPPR outperforms the current edge-based personalized PageRank methodology.

1 December 2009
Verified
Conference Paper
Closed access
MBMohsen Bayati
Mohsen Bayati
MGMargot Gerritsen
Margot Gerritsen
DGDavid F. Gleich
David F. Gleich
ASAmin Saberi
Amin Saberi
YWYing Wang
Ying Wang
We propose a new distributed algorithm for sparse variants of the network alignment problem, which occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for this NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.

17 July 2012 in Numerical Linear Algebra with Applications
Verified
Journal Article
Closed access
PDF file
DGDavid F. Gleich
David F. Gleich
CGChen Greif
Chen Greif
JVJames M. Varah
James M. Varah

4 September 2014 in PLOS ONE
Verified
Journal Article
Open access
PDF file
ABAnthony Bonato
Anthony Bonato
DGDavid F. Gleich
David F. Gleich
MKMyunghwan Kim
Myunghwan Kim
DMDieter Mitsche
Dieter Mitsche
PPPaweł Prałat
Paweł Prałat
SYStephen J. Young
Stephen J. Young
We consider the dimensionality of social networks, and develop experiments aimed at predicting that dimension. We find that a social network model with nodes and links sampled from an m-dimensional metric space with power-law distributed influence regions best fits samples from real-world networks when m scales logarithmically with the number of nodes of the network. This supports a logarithmic dimension hypothesis, and we provide evidence with two different social networks, Facebook and LinkedIn. Further, we employ two different methods for confirming the hypothesis: the first uses the distribution of motif counts, and the second exploits the eigenvalue distribution.

28 July 2016 in IEEE/ACM Transactions on Computational Biology and Bioinformatics
Verified
Journal Article
Open access
SMShahin Mohammadi
Shahin Mohammadi
DGDavid F. Gleich
David F. Gleich
TKTamara G. Kolda
Tamara G. Kolda
AGAnanth Grama
Ananth Grama
Network alignment has extensive applications in comparative interactomics. Traditional approaches aim to simultaneously maximize the number of conserved edges and the underlying similarity of aligned entities. We propose a novel formulation of the network alignment problem that extends topological similarity to higher-order structures and provides a new objective function that maximizes the number of aligned substructures. This objective function corresponds to an integer programming problem, which is NP-hard. Consequently, we identify a closely related surrogate function whose maximization results in a tensor eigenvector problem. Based on this formulation, we present an algorithm called Triangular AlignMEnt (TAME), which attempts to maximize the number of aligned triangles across networks. Using a case study on the NAPAbench dataset, we show that triangular alignment is capable of producing mappings with high node correctness. We further evaluate our method by aligning yeast and human interactomes. Our results indicate that TAME outperforms the state-of-art alignment methods in terms of conserved triangles. In addition, we show that the number of conserved triangles is more significantly correlated, compared to the conserved edge, with node correctness and co-expression of edges. Our formulation and resulting algorithms can be easily extended to arbitrary motifs.

6 August 2018 in IEEE Transactions on Pattern Analysis and Machine Intelligence
Verified
Journal Article
Closed access
JWJoyce Jiyoung Whang
Joyce Jiyoung Whang
YHYangyang Hou
Yangyang Hou
DGDavid F. Gleich
David F. Gleich
IDInderjit S. Dhillon
Inderjit S. Dhillon
Traditional clustering algorithms, such as K-Means, output a clustering that is disjoint and exhaustive, i.e., every single data point is assigned to exactly one cluster. However, in many real-world datasets, clusters can overlap and there are often outliers that do not belong to any cluster. While this is a well-recognized problem, most existing algorithms address either overlap or outlier detection and do not tackle the problem in a unified way. In this paper, we propose an intuitive objective function, which we call the NEO-K-Means (Non-Exhaustive, Overlapping K-Means) objective, that captures the issues of overlap and non-exhaustiveness in a unified manner. Our objective function can be viewed as a reformulation of the traditional K-Means objective, with easy-to-understand parameters that capture the degrees of overlap and non-exhaustiveness. By considering an extension to weighted kernel K-Means, we show that we can also apply our NEO-K-Means idea to overlapping community detection, which is an important task in network analysis. To optimize the NEO-K-Means objective, we develop not only fast iterative algorithms but also more sophisticated algorithms using low-rank semidefinite programming techniques. Our experimental results show that the new objective and algorithms are effective in finding ground-truth clusterings that have varied overlap and non-exhaustiveness; for the case of graphs, we show that our method outperforms state-of-the-art overlapping community detection algorithms.