Arrow Research search

Author name cluster

John E. Hopcroft

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

NeurIPS Conference 2024 Conference Paper

Leveraging Contrastive Learning for Enhanced Node Representations in Tokenized Graph Transformers

  • Jinsong Chen
  • Hanpeng Liu
  • John E. Hopcroft
  • Kun He

While tokenized graph Transformers have demonstrated strong performance in node classification tasks, their reliance on a limited subset of nodes with high similarity scores for constructing token sequences overlooks valuable information from other nodes, hindering their ability to fully harness graph information for learning optimal node representations. To address this limitation, we propose a novel graph Transformer called GCFormer. Unlike previous approaches, GCFormer develops a hybrid token generator to create two types of token sequences, positive and negative, to capture diverse graph information. And a tailored Transformer-based backbone is adopted to learn meaningful node representations from these generated token sequences. Additionally, GCFormer introduces contrastive learning to extract valuable information from both positive and negative token sequences, enhancing the quality of learned node representations. Extensive experimental results across various datasets, including homophily and heterophily graphs, demonstrate the superiority of GCFormer in node classification, when compared to representative graph neural networks (GNNs) and graph Transformers.

PDF Details DOI

ICML Conference 2023 Conference Paper

On the Complexity of Bayesian Generalization

  • Yu-Zhe Shi
  • Manjie Xu
  • John E. Hopcroft
  • Kun He 0001
  • Joshua B. Tenenbaum
  • Song-Chun Zhu
  • Ying Nian Wu
  • Wenjuan Han

We examine concept generalization at a large scale in the natural visual spectrum. Established computational modes ( i. e. , rule-based or similarity-based) are primarily studied isolated, focusing on confined and abstract problem spaces. In this work, we study these two modes when the problem space scales up and when the complexity of concepts becomes diverse. At the representational level, we investigate how the complexity varies when a visual concept is mapped to the representation space. Prior literature has shown that two types of complexities (Griffiths & Tenenbaum, 2003) build an inverted-U relation (Donderi, 2006; Sun & Firestone, 2021). Leveraging Representativeness of Attribute (RoA), we computationally confirm: Models use attributes with high RoA to describe visual concepts, and the description length falls in an inverted-U relation with the increment in visual complexity. At the computational level, we examine how the complexity of representation affects the shift between the rule- and similarity-based generalization. We hypothesize that category-conditioned visual modeling estimates the co-occurrence frequency between visual and categorical attributes, thus potentially serving as the prior for the natural visual world. Experimental results show that representations with relatively high subjective complexity outperform those with relatively low subjective complexity in rule-based generalization, while the trend is the opposite in similarity-based generalization.

Details

ICLR Conference 2020 Conference Paper

Nesterov Accelerated Gradient and Scale Invariance for Adversarial Attacks

  • Jiadong Lin
  • Chuanbiao Song
  • Kun He 0001
  • Liwei Wang 0001
  • John E. Hopcroft

Deep learning models are vulnerable to adversarial examples crafted by applying human-imperceptible perturbations on benign inputs. However, under the black-box setting, most existing adversaries often have a poor transferability to attack other defense models. In this work, from the perspective of regarding the adversarial example generation as an optimization process, we propose two new methods to improve the transferability of adversarial examples, namely Nesterov Iterative Fast Gradient Sign Method (NI-FGSM) and Scale-Invariant attack Method (SIM). NI-FGSM aims to adapt Nesterov accelerated gradient into the iterative attacks so as to effectively look ahead and improve the transferability of adversarial examples. While SIM is based on our discovery on the scale-invariant property of deep learning models, for which we leverage to optimize the adversarial perturbations over the scale copies of the input images so as to avoid "overfitting” on the white-box model being attacked and generate more transferable adversarial examples. NI-FGSM and SIM can be naturally integrated to build a robust gradient-based attack to generate more transferable adversarial examples against the defense models. Empirical results on ImageNet dataset demonstrate that our attack methods exhibit higher transferability and achieve higher attack success rates than state-of-the-art gradient-based attacks.

Details

ICLR Conference 2020 Conference Paper

Robust Local Features for Improving the Generalization of Adversarial Training

  • Chuanbiao Song
  • Kun He 0001
  • Jiadong Lin
  • Liwei Wang 0001
  • John E. Hopcroft

Adversarial training has been demonstrated as one of the most effective methods for training robust models to defend against adversarial examples. However, adversarially trained models often lack adversarially robust generalization on unseen testing data. Recent works show that adversarially trained models are more biased towards global structure features. Instead, in this work, we would like to investigate the relationship between the generalization of adversarial training and the robust local features, as the robust local features generalize well for unseen shape variation. To learn the robust local features, we develop a Random Block Shuffle (RBS) transformation to break up the global structure features on normal adversarial examples. We continue to propose a new approach called Robust Local Features for Adversarial Training (RLFAT), which first learns the robust local features by adversarial training on the RBS-transformed adversarial examples, and then transfers the robust local features into the training of normal adversarial examples. To demonstrate the generality of our argument, we implement RLFAT in currently state-of-the-art adversarial training frameworks. Extensive experiments on STL-10, CIFAR-10 and CIFAR-100 show that RLFAT significantly improves both the adversarially robust generalization and the standard generalization of adversarial training. Additionally, we demonstrate that our models capture more local features of the object on the images, aligning better with human perception.

Details

ICLR Conference 2016 Conference Paper

Convergent Learning: Do different neural networks learn the same representations?

  • Yixuan Li 0001
  • Jason Yosinski
  • Jeff Clune
  • Hod Lipson
  • John E. Hopcroft

Recent success in training deep neural networks have prompted active investigation into the features learned on their intermediate layers. Such research is difficult because it requires making sense of non-linear computations performed by millions of parameters, but valuable because it increases our ability to understand current models and create improved versions of them. In this paper we investigate the extent to which neural networks exhibit what we call convergent learning, which is when the representations learned by multiple nets converge to a set of features which are either individually similar between networks or where subsets of features span similar low-dimensional spaces. We propose a specific method of probing representations: training multiple networks and then comparing and contrasting their individual, learned representations at the level of neurons or groups of neurons. We begin research into this question using three techniques to approximately align different neural networks on a feature level: a bipartite matching approach that makes one-to-one assignments between neurons, a sparse prediction approach that finds one-to-many mappings, and a spectral clustering approach that finds many-to-many mappings. This initial investigation reveals a few previously unknown properties of neural networks, and we argue that future research into the question of convergent learning will yield many more. The insights described here include (1) that some features are learned reliably in multiple networks, yet other features are not consistently learned; (2) that units learn to span low-dimensional subspaces and, while these subspaces are common to multiple networks, the specific basis vectors learned are not; (3) that the representation codes show evidence of being a mix between a local code and slightly, but not fully, distributed codes across multiple units.

Details

FOCS Conference 2005 Conference Paper

On Learning Mixtures of Heavy-Tailed Distributions

  • Anirban Dasgupta 0001
  • John E. Hopcroft
  • Jon M. Kleinberg
  • Mark Sandler 0002

We consider the problem of learning mixtures of arbitrary symmetric distributions. We formulate sufficient separation conditions and present a learning algorithm with provable guarantees for mixtures of distributions that satisfy these separation conditions. Our bounds are independent of the variances of the distributions; to the best of our knowledge, there were no previous algorithms known with provable learning guarantees for distributions having infinite variance and/or expectation. For Gaussians and log-concave distributions, our results match the best known sufficient separation conditions by D. Achlioptas and F. McSherry (2005) and S. Vempala and G. Wang (2004). Our algorithm requires a sample of size O/spl tilde/(dk), where d is the number of dimensions and k is the number of distributions in the mixture. We also show that for isotropic power-laws, exponential, and Gaussian distributions, our separation condition is optimal up to a constant factor.

Details

FOCS Conference 2004 Conference Paper

Spectral Analysis of Random Graphs with Skewed Degree Distributions

  • Anirban Dasgupta 0001
  • John E. Hopcroft
  • Frank McSherry

We extend spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian. The normalization is based on intuition drawn from perturbation theory of random matrices, and has the effect of boosting the expectation of the random adjacency matrix without increasing the variances of its entries, leading to better perturbation bounds. The primary implication of this result lies in the realm of spectral analysis of random graphs with skewed degree distributions, such as the ubiquitous "power law graphs". Mihail and Papadimitriou (2002) argued that for randomly generated graphs satisfying a power law degree distribution, spectral analysis of the adjacency matrix simply produces the neighborhoods of the high degree nodes as its eigenvectors, and thus miss any embedded structure. We present a generalization of their model, incorporating latent structure, and prove that after applying our transformation, spectral analysis succeeds in recovering the latent structure with high probability.

Details

FOCS Conference 1982 Conference Paper

Fast Parallel Matrix and GCD Computations

  • Allan Borodin
  • Joachim von zur Gathen
  • John E. Hopcroft

We present parallel algorithms to compute the determinant and characteristic polynomial of n×n-matrices and the gcd of polynomials of degree ≤n. The algorithms use parallel time O(log2n) and a polynomial number of processors. We also give a fast parallel Las Vegas algorithm for the rank of matrices. All algorithms work over arbitrary fields.

Details

FOCS Conference 1982 Conference Paper

On the Movement of Robot Arms in 2-Dimensional Bounded Regions

  • John E. Hopcroft
  • Deborah Joseph
  • Sue Whitesides

The classical mover's problem is the following: can a rigid object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version of this problem involving objects with movable joints is PSPACE-complete, even for a simple tree-like structure. In this paper, we investigate a 2-dimensional mover's problem in which the object being moved is a robot arm with an arbitrary number of joints. We reduce the mover's problem for arms constrained to move within bounded regions whose boundaries are made up of straight lines to the mover's problem for a more complex linkage that is not constrained. We prove that the latter problem is PSPACE-hard even in 2-dimensional space and then turn to special cases of the mover's problem for arms. In particular, we give a polynomial time algorithm for moving an arm confined within a circle from one given configuration to another. We also give a polynomial time algorithm for moving the arm from its initial position to a position in which the end of the arm reaches a given point within the circle.

Details

FOCS Conference 1980 Conference Paper

Polynomial-Time Algorithms for Permutation Groups

  • Merrick L. Furst
  • John E. Hopcroft
  • Eugene M. Luks

A permutation group on n letters may always be represented by a small set of generators, even though its size may be exponential in n. We show that it is practical to use such a representation since many problems such as membership testing, equality testing, and inclusion testing are decidable in polynomial time. In addition, we demonstrate that the normal closure of a subgroup can be computed in polynomial time, and that this proceaure can be used to test a group for solvability. We also describe an approach to computing the intersection of two groups. The procedures and techniques have wide applicability and have recently been used to improve many graph isomorphism algorithms.

Details

STOC Conference 1974 Conference Paper

Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report)

  • John E. Hopcroft
  • J. K. Wong

The isomorphism problem for graphs G 1 and G 2 is to determine if there exists a one-to-one mapping of the vertices of G 1 onto the vertices of G 2 such that two vertices of G 1 are adjacent if and only if their images in G 2 are adjacent. In addition to determining the existence of such an isomorphism, it is useful to be able to produce an isomorphism-inducing mapping in the case where one exists.

Details
v2026.09.13