Publications
Please refer here for an up-to date list.
Compact and Informative Representation of Functional Connectivity for Predictive Modeling
Raif Rustamov, David Romano, Allan Reiss, and Leonidas Guibas
MICCAI 2014
Resting state functional connectivity holds great potential for diagnostic prediction of neurological and psychiatric illness. This paper introduces a compact and information-rich representation of connectivity that is geared directly towards predictive modeling. Our representation does not require a priori identification of localized regions of interest, yet provides a mechanism for interpretation of classifier weights. Experiments confirm increased accuracy associated with our representation and yield interpretations consistent with known physiology.
Wasserstein Propagation for Semi-Supervised Learning
Justin Solomon, Raif Rustamov, Leonidas Guibas, Adrian Butscher
ICML 2014
Probability distributions and histograms are natural representations for product ratings, traffic measurements, and other data considered in many machine learning applications. Thus, this paper introduces a technique for graph-based semisupervised learning of histograms, derived from the theory of optimal transportation. Our method has several properties making it suitable for this application; in particular, its behavior can be characterized by the moments and shapes of the histograms at the labeled nodes. In addition, it can be used for histograms on non-standard domains like circles, revealing a strategy for manifold-valued semi-supervised learning. We also extend this technique to related problems such as smoothing distributions on graph nodes.
Hyperalignment of Multi-Subject fMRI Data by Synchronized Projections
Raif Rustamov and Leonidas Guibas
NIPS Workshop on Machine Learning and Interpretation in Neuroimaging, MLINI 2013; best paper runner-up
Group analysis of fMRI data via multivariate pattern methods requires accurate alignments between neuronal activities of different subjects in order to attain competitive inter-subject classification rates. Hyperalignment, a recent technique pioneered by Haxby and collaborators, aligns the activations of different subjects by mapping them into a common abstract high-dimensional space. While hyperalignment is very successful in terms of classification performance, its “anatomy free” nature excludes the use of potentially helpful information inherent in anatomy. In this paper, we present a novel approach to hyperalignment that allows incorporating anatomical information in a non-trivial way. Experiments demonstrate the effectiveness of our approach over the original hyperalignment and several other natural alternatives.
Wavelets on Graphs via Deep Learning
Raif Rustamov and Leonidas Guibas
NIPS 2013
An increasing number of applications require processing of signals defined on weighted graphs. While wavelets provide a flexible tool for signal processing in the classical setting of regular domains, the existing graph wavelet constructions are less flexible -- they are guided solely by the structure of the underlying graph and do not take directly into consideration the particular class of signals to be processed. This paper introduces a machine learning framework for constructing graph wavelets that can sparsely represent a given class of signals. Our construction uses the lifting scheme, and is based on the observation that the recurrent nature of the lifting scheme gives rise to a structure resembling a deep auto-encoder network. Particular properties that the resulting wavelets must satisfy determine the training objective and the structure of the involved neural networks. The training is unsupervised, and is conducted similarly to the greedy pre-training of a stack of auto-encoders. After training is completed, we obtain a linear wavelet transform that can be applied to any graph signal in time and memory linear in the size of the graph. Improved sparsity of our wavelet transform for the test signals is confirmed via experiments both on synthetic and real data.
Map-Based Exploration of Intrinsic Shape Differences and Variability
Raif Rustamov, Maks Ovsjanikov, Omri Azencot, Mirela Ben-Chen, Frederic Chazal, and Leonidas Guibas
SIGGRAPH 2013
We develop a novel formulation for the notion of shape differences, aimed at providing detailed information about the location and nature of the differences or distortions between the two shapes being compared. Our difference operator, derived from a shape map, is much more informative than just a scalar global shape similarity score, rendering it useful in a variety of applications where more refined shape comparisons are necessary. The approach is intrinsic and is based on a linear algebraic framework, allowing the use of many common linear algebra tools (e.g, SVD, PCA) for studying a matrix representation of the operator. Remarkably, the formulation allows us not only to localize shape differences on the shapes involved, but also to compare shape differences across pairs of shapes, and to analyze the variability in entire shape collections based on the differences between the shapes. Moreover, while we use a map or correspondence to define each shape difference, consistent correspondences between the shapes are not necessary for comparing shape differences, although they can be exploited if available. We give a number of applications of shape differences, including parameterizing the intrinsic variability in a shape collection, exploring shape collections using local variability at different scales, performing shape analogies, and aligning shape collections.
Paper Presentation Sample Code
Graph Matching with Anchor Nodes: A Learning Approach
Nan Hu, Raif Rustamov, and Leonidas Guibas
CVPR2013
In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widely-used image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
Average Interpolating Wavelets on Point Clouds and Graphs
arXiv preprint, arXiv:1110.2227v1 [math.FA]
We introduce a new wavelet transform suitable for analyzing functions on point clouds and graphs. Our construction is based on a generalization of the average interpolating refinement scheme of Donoho. The most important ingredient of the original scheme that needs to be altered is the choice of the interpolant. Here, we define the interpolant as the minimizer of a smoothness functional, namely a generalization of the Laplacian energy, subject to the averaging constraints. In the continuous setting, we derive a formula for the optimal solution in terms of the poly-harmonic Green's function. The form of this solution is used to motivate our construction in the setting of graphs and point clouds. We highlight the empirical convergence of our refinement scheme and the potential applications of the resulting wavelet transform through experiments on a number of data stets.
Multiscale Biharmonic Kernels
SGP Best Paper Award, 3rd place
Computer Graphics Forum (Symposium on Geometry Processing), Volume 30, Number 5 (July 2011).
This paper introduces a general principle for constructing multiscale kernels on surface meshes, and presents a construction of the multiscale pre-biharmonic and multiscale biharmonic kernels. Our construction is based on an optimization problem that seeks to minimize a smoothness criterion, the Laplacian energy, subject to a sparsity inducing constraint. Namely, we use the lasso constraint, which sets an upper bound on the L1-norm of the solution, to obtain a family of solutions parametrized by this upper-bound parameter. The interplay between sparsity and smoothness results in smooth kernels that vanish away from the diagonal. We prove that the resulting kernels have gradually changing supports, consistent behavior over partial and complete meshes, and interesting limiting behaviors (e.g. in the limit of large scales, the multiscale biharmonic kernel converges to the Green's function of the biharmonic equation); in addition, these kernels are based on intrinsic quantities and so are insensitive to isometric deformations. We show empirically that our kernels are shape-aware, are robust to noise, tessellation, and partial object, and are fast to compute. Finally, we demonstrate that the new kernels can be useful for function interpolation and shape correspondence.
Paper
Interpolated Eigenfunctions for Volumetric Shape Processing
To appear in The Visual Computer
Abstract This paper introduces a set of volumetric functions suitable for geometric processing of volumes. We start with Laplace-Beltrami eigenfunctions on the bounding surface and interpolate them into the interior using barycentric coordinates. The interpolated eigenfunctions: 1) can be computed efficiently by using the boundary mesh only; 2) can be seen as a shape-aware generalization of barycentric coordinates; 3) can be used for efficiently representing volumetric functions; 4) can be naturally plugged into existing spectral embedding constructions such as the diffusion embedding to provide their volumetric counterparts. Using the interior diffusion embedding we define the interior Heat Kernel Signature (iHKS) and examine its performance for the task of volumetric point correspondence. We show that the three main qualities of the surface Heat Kernel Signature -- being informative, multiscale, and insensitive to pose -- are inherited by this volumetric construction. Finally, we construct a bag of features based shape descriptor that aggregates the iHKS signatures over the volume of a shape, and evaluate its performance on a public shape retrieval benchmark. We find that while, theoretically, strict isometry invariance requires concentrating on the intrinsic surface properties alone, yet, practically, pose insensitive shape retrieval can be achieved using volumetric information.
Paper
A Versatile Framework for Shape Description
The Visual Computer, Volume 26, Number 10, 1245-1256
We present a shape description framework that generates a multitude of shape descriptors through a variety of design and continuum of parameter choices. Our parameter is a surface mesh, referred to as template, which is supplied at run time, and allows generating different shape descriptors for the same model. Our framework extracts a numerical shape descriptor by computing a selected function on the model mesh, mapping (transferring) it to the template, expanding the mapped function in terms of a basis on the template, and collecting the expansion coefficients into a vector. We investigate possible design choices for the steps in the framework, and introduce novel approaches that provide further freedom in generating a multitude of previously unknown descriptors. We show that our approach is a generalization of the way some of the existing numerical descriptors are defined, and that for appropriate template choices one is able to reproduce some of the well-known descriptors. Finally, we show empirically that design and parameter choices have non-trivial effects on the descriptor's performance, and that better retrieval results can be obtained by combining descriptors obtained via different templates.
Paper
Barycentric Coordinates on Surfaces
Computer Graphics Forum (Symposium on Geometry Processing), Volume 29, Number 5 (July 2010).
This paper introduces a method for defining and efficiently computing barycentric coordinates with respect to polygons on general surfaces. Our construction is geared towards injective polygons (polygons that can be enclosed in a metric ball of an appropriate size) and is based on replacing the linear precision property of planar coordinates by a requirement in terms of center of mass, and generalizing this requirement to the surface setting. We show that the resulting surface barycentric coordinates can be computed using planar barycentric coordinates with respect to a polygon in the tangent plane. We prove theoretically that the surface coordinates properly generalize the planar coordinates and carry some of their useful properties such as unique reconstruction of a point given its coordinates, uniqueness for triangles, edge linearity, similarity invariance, and smoothness; in addition, these coordinates are insensitive to isometric deformations and can be used to reconstruct isometries. We show empirically that surface coordinates are shape-aware with consistent gross behavior across different surfaces, are well-behaved for different polygon types/locations on variety of surface forms, and that they are fast to compute. Finally, we demonstrate effectiveness of surface coordinates for interpolation, decal mapping, and correspondence refinement.
Paper Presentation (PPTX)
Biharmonic Distance
Yaron Lipman*, Raif Rustamov*, and Thomas Funkhouser
*equal contribution
ACM Transactions on Graphics, Volume 29, Issue 3 (June 2010).
Measuring distances between pairs of points on a 3D surface is a fundamental problem in computer graphics and geometric processing. For most applications, the important properties of a distance are that it is a metric, smooth, locally isotropic, globally "shape-aware", isometry invariant, insensitive to noise and small topology changes, parameter-free, and practical to compute on a discrete mesh. However, the basic methods currently popular in computer graphics (e.g., geodesic and diffusion distances) do not have these basic properties. In this paper, we propose a new distance measure based on the biharmonic differential operator that has all the desired properties. This new surface distance is related to the diffusion and commute-time distances, but applies different (inverse squared) weighting to the eigenvalues of the Laplace-Beltrami operator, which provides a nice trade-off between nearly geodesic distances for small distances and global shape-awareness for large distances. The paper provides theoretical and empirical analysis for a large number of meshes.
Paper Code
Robust Volumetric Shape Descriptor
Eurographics 3DOR 2010
This paper introduces a volume-based shape descriptor that is robust with respect to changes in pose and topology. We use modified shape distributions in conjunction with the interior distances and barycentroid potential that are based on barycentric coordinates. In our approach, shape distributions are aggregated throughout the entire volume contained within the shape thus capturing information conveyed by the volumes of shapes. Since interior distances and barycentroid potential are practically insensitive to various poses/deformations and to non-pervasive topological changes (addition of small handles), our shape descriptor inherits such insensitivity as well. In addition, if any other modes of information (e.g. electrostatic potential within the protein volume) are available, they can be easily incorporated into the descriptor as additional dimensions in the histograms. Our descriptor has a connection to an existing surface based shape descriptor, the Global Point Signatures (GPS). We use this connection to fairly examine the value of volumetric information for shape retrieval. We find that while, theoretically, strict isometry invariance requires concentrating on the intrinsic surface properties alone, yet, practically, pose insensitive shape retrieval still can be achieved/enhanced using volumetric information.
Paper
Barycentric coordinate with respect to the vertex v1
of a surface triangle.
Interior Distance Using Barycentric Coordinates
Raif Rustamov, Yaron Lipman, and Thomas Funkhouser
Computer Graphics Forum (Symposium on Geometry Processing), 2009.
This paper introduces a framework for defining a shape-aware distance measure between any two points in the interior of a surface mesh. Our framework is based on embedding the surface mesh into a high-dimensional space in a way that best preserves boundary distances between vertices of the mesh, performing a mapping of the mesh volume into this high-dimensional space using barycentric coordinates, and defining the interior distance between any two points simply as their Euclidean distance in the embedding space.We investigate the theoretical properties of the interior distance in relation to properties of the chosen boundary distances and barycentric coordinates, and we investigate empirical properties of the interior distance using diffusion distance as the prescribed boundary distance and mean value coordinates.We prove theoretically that the interior distance is a metric, smooth, interpolating the boundary distances, and reproducing Euclidean distances, and we show empirically that it is insensitive to boundary noise and deformation and quick to compute. In case the barycentric coordinates are non-negative we also show a maximum principle exists. Finally, we use it to define a new geometric property, barycentroid of shape, and show that it captures the notion of semantic center of the shape.
Paper Presentation (PPTX) Code
On Mesh Editing, Manifold Learning, and Diffusion Wavelets
IMA Conference on the Mathematics of Surfaces, 2009
We spell out a formal equivalence between the naive Laplacian editing and semi-supervised learning by bi-Laplacian Regularized Least Squares. This allows us to write the solution to Laplacian mesh editing in a “closed” form, based on which we introduce the Generalized Linear Editing (GLE). GLE has both naive Laplacian editing and gradient based editing as special cases. GLE allows using diffusion wavelets for mesh editing. We present preliminary experiments, and shortly discuss connections to segmentation.
Paper
Template Based Shape Descriptor
Eurographics Workshop on 3D Object Retrieval 2009
We introduce a new 3D shape descriptor which maps the surface features onto an arbitrary template surface using mean-value interpolation. A compact numerical shape descriptor is extracted using manifold harmonics on the template. We show that mean-value interpolation is a strong alternative to the often used projection. The utility of using different templates is established by showing that concatenating descriptors coming from different templates improves retrieval quality.
Paper Presentation
Rapid comparison of properties on protein surface
Sael L, La D, Li B, Rustamov R, Kihara D.
Proteins. Volume 73, Number 1 / October, 2008
The mapping of physicochemical characteristics onto the surface of a protein provides crucial insights into its function and evolution. This information can be further used in the characterization and identification of similarities within protein surface regions. We propose a novel method which quantitatively compares global and local properties on the protein surface. We have tested the method on comparison of electrostatic potentials and hydrophobicity. The method is based on 3D Zernike descriptors, which provides a compact representation of a given property defined on a protein surface. Compactness and rotational invariance of this descriptor enable fast comparison suitable for database searches. The usefulness of this method is exemplified by studying several protein families including globins, thermophilic and mesophilic proteins, and active sites of TIM beta/alpha barrel proteins. In all the cases studied, the descriptor is able to cluster proteins into functionally relevant groups. The proposed approach can also be easily extended to other surface properties. This protein surface-based approach will add a new way of viewing and comparing proteins to conventional methods, which compare proteins in terms of their primary sequence or tertiary structure.
Paper
Fast protein tertiary structure retrieval based on global surface shape similarity
Sael L, Li B, La D, Fang Y, Ramani K, Rustamov R, Kihara D.
Proteins. Volume 72, Number 4 / September, 2008
Characterization and identification of similar tertiary structure of proteins provides rich information for investigating function and evolution. The importance of structure similarity searches is increasing as structure databases continue to expand, partly due to the structural genomics projects. A crucial drawback of conventional protein structure comparison methods, which compare structures by their main-chain orientation or the spatial arrangement of secondary structure, is that a database search is too slow to be done in real-time. Here we introduce a global surface shape representation by three-dimensional (3D) Zernike descriptors, which represent a protein structure compactly as a series expansion of 3D functions. With this simplified representation, the search speed against a few thousand structures takes less than a minute. To investigate the agreement between surface representation defined by 3D Zernike descriptor and conventional main-chain based representation, a benchmark was performed against a protein classification generated by the combinatorial extension algorithm. Despite the different representation, 3D Zernike descriptor retrieved proteins of the same conformation defined by combinatorial extension in 89.6% of the cases within the top five closest structures. The real-time protein structure search by 3D Zernike descriptor will open up new possibility of large-scale global and local protein surface shape comparison.
Paper 3D Surfer: Protein search engine
On Manifold Learning and Mesh Editing
Poster at SGP 2008
We notice a formal connection between two fields -- manifold learning and mesh editing, and exploit this connection to introduce a generalization of the naive Laplacian mesh editing.
Augmented Planar Reflective Symmetry Transforms
The Visual Computer, Volume 24, Number 6/June, 2008
Symmetry has been playing an increasing role in 3D shape processing. Recently introduced planar reflective symmetry transform (PRST) has been found useful for canonical coordinate frame determination, shape matching, retrieval, and segmentation. Guided by the intuition that every imperfect symmetry is imperfect in its own way, we investigate the possibility of incorporating more information into symmetry transforms like PRST. As a step in this direction, the concept of augmented symmetry transform is introduced; we obtain a family of symmetry transforms indexed by a parameter. While the original PRST measures how much the symmetry is broken, the augmented PRST also gives some information about how it is broken. Several approaches to calculating the augmented transform are described. We demonstrate that the augmented transform is beneficial for shape retrieval.
Paper
Boundary Element Formulation of Harmonic Coordinates
Technical Report, November, 2007
We explain how Boundary Element Methods (BEM) can be used to speed up the computation and reduce the storage associated with Harmonic Coordinates. In addition, BEM formulation allows extending the harmonic coordinates to the exterior and makes possible to compare the transfinite harmonic coordinates with transfinite Shepard interpolation and Mean Value Coordinates. This comparison reveals that there are unifying formulas, yet harmonic coordinates belong to a fundamentally different end of the spectrum. This observation allows us to generalize harmonic coordinates by introducing a novel class of interpolates which we call weakly singular interpolates.
Technical Report
Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation
SGP 2007
A deformation invariant representation of surfaces, the GPS embedding, is introduced using the eigenvalues and eigenfunctions of the Laplace-Beltrami differential operator. Notably, since the definition of the GPS embedding completely avoids the use of geodesic distances, and is based on objects of global character, the obtained representation is robust to local topology changes. The GPS embedding captures enough information to handle various shape processing tasks as shape classification, segmentation, and correspondence. To demonstrate the practical relevance of the GPS embedding, we introduce a deformation invariant shape descriptor called G2-distributions, and demonstrate their discriminative power, invariance under natural deformations, and robustness.
Paper Presentation (PPT)
Augmented Symmetry Transforms
SMI 2007
Symmetry has been playing an increasing role in 3D shape processing. Recently introduced Planar Reflective Symmetry Transform(PRST) has been found useful for canonical coordinate frame determination, shape matching, retrieval, and segmentation. Guided by the intuition that every imperfect symmetry is imperfect in its own way, we investigate the possibility of incorporating more information into symmetry transforms like PRST. As a step in this direction, the concept of Augmented Symmetry Transform is introduced; we obtain a family of symmetry transforms indexed by a parameter. While the original PRST measures how much the symmetry is broken, the Augmented PRST also gives some information about how it is broken. Several approaches to calculating the augmented transform are described. We demonstrate that the augmented transform is useful for shape retrieval.
Paper Presentation (PPT)
Work in Topology
My PhD work concentrated on low-dimensional topology, specifically, Heegaard Floer homology and its interplay with singularity theory and symplectic geometry.
The Renormalized Euler Characteristic and L-space Surgeries.
