Author name cluster

John 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.

9 papers

1 author row

NeurIPS Conference 2025 Conference Paper

Rethinking Tokenized Graph Transformers for Node Classification

Jinsong Chen
Chenyang Li
Gaichao Li
John Hopcroft
Kun He

Node tokenized graph Transformers (GTs) have shown promising performance in node classification. The generation of token sequences is the key module in existing tokenized GTs which transforms the input graph into token sequences, facilitating the node representation learning via Transformer. In this paper, we observe that the generations of token sequences in existing GTs only focus on the first-order neighbors on the constructed similarity graphs, which leads to the limited usage of nodes to generate diverse token sequences, further restricting the potential of tokenized GTs for node classification. To this end, we propose a new method termed SwapGT. SwapGT first introduces a novel token swapping operation based on the characteristics of token sequences that fully leverages the semantic relevance of nodes to generate more informative token sequences. Then, SwapGT leverages a Transformer-based backbone to learn node representations from the generated token sequences. Moreover, SwapGT develops a center alignment loss to constrain the representation learning from multiple token sequences, further enhancing the model performance. Extensive empirical results on various datasets showcase the superiority of SwapGT for node classification. Code is available at https: //github. com/JHL-HUST/SwapGT.

PDF Details

NeurIPS Conference 2022 Conference Paper

Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power

Binghui Li
Jikai Jin
Han Zhong
John Hopcroft
Liwei Wang

It is well-known that modern neural networks are vulnerable to adversarial examples. To mitigate this problem, a series of robust learning algorithms have been proposed. However, although the robust training error can be near zero via some methods, all existing algorithms lead to a high robust generalization error. In this paper, we provide a theoretical understanding of this puzzling phenomenon from the perspective of expressive power for deep neural networks. Specifically, for binary classification problems with well-separated data, we show that, for ReLU networks, while mild over-parameterization is sufficient for high robust training accuracy, there exists a constant robust generalization gap unless the size of the neural network is exponential in the data dimension $d$. This result holds even if the data is linear separable (which means achieving standard generalization is easy), and more generally for any parameterized function classes as long as their VC dimension is at most polynomial in the number of parameters. Moreover, we establish an improved upper bound of $\exp({\mathcal{O}}(k))$ for the network size to achieve low robust generalization error when the data lies on a manifold with intrinsic dimension $k$ ($k \ll d$). Nonetheless, we also have a lower bound that grows exponentially with respect to $k$ --- the curse of dimensionality is inevitable. By demonstrating an exponential separation between the network size for achieving low robust training and generalization error, our results reveal that the hardness of robust generalization may stem from the expressive power of practical models.

PDF Details

TCS Journal 2018 Journal Article

Neighbourhood-preserving dimension reduction via localised multidimensional scaling

Yuzhe Ma
Kun He
John Hopcroft
Pan Shi

When high-dimensional data has an intrinsic lower-dimensional manifold structure, one can incorporate such structure knowledge into dimension reduction and design algorithms for special purposes, e. g. , preserving the local neighbourhood or uncovering the global structure of data. Based on such assumption, we propose a neighbourhood-preserving dimension reduction algorithm, Localised Multidimensional Scaling with BFS (LMB), for generating low dimensional representation of data that has a latent manifold structure. LMB applies the Multidimensional Scaling (MDS) on the local neighbourhood of data and stitches the reduced neighbourhoods together to form a global reduction. By analysing the local structure of data, LMB can automatically find a well-fit space for reduction. We thoroughly compare the performance of LMB with other state-of-the-art linear or nonlinear algorithms on both synthetic data and real data. Numerical experiments show that LMB efficiently preserves the neighbourhood while uncovering the embedded structure of data. LMB also has a low complexity of O ( n 2 ) for a n-item data set.

Details DOI

NeurIPS Conference 2018 Conference Paper

Towards Understanding Learning Representations: To What Extent Do Different Neural Networks Learn the Same Representation

Liwei Wang
Lunjia Hu
Jiayuan Gu
Zhiqiang Hu
Yue Wu
Kun He
John Hopcroft

It is widely believed that learning good representations is one of the main reasons for the success of deep neural networks. Although highly intuitive, there is a lack of theory and systematic approach quantitatively characterizing what representations do deep neural networks learn. In this work, we move a tiny step towards a theory and better understanding of the representations. Specifically, we study a simpler problem: How similar are the representations learned by two networks with identical architecture but trained from different initializations. We develop a rigorous theory based on the neuron activation subspace match model. The theory gives a complete characterization of the structure of neuron activation subspace matches, where the core concepts are maximum match and simple match which describe the overall and the finest similarity between sets of neurons in two networks respectively. We also propose efficient algorithms to find the maximum match and simple matches. Finally, we conduct extensive experiments using our algorithms. Experimental results suggest that, surprisingly, representations learned by the same convolutional layers of networks trained from different initializations are not as similar as prevalently expected, at least in terms of subspace match.

PDF Details

NeurIPS Conference 2016 Conference Paper

A Powerful Generative Model Using Random Weights for the Deep Image Representation

Kun He
Yan Wang
John Hopcroft

To what extent is the success of deep visualization due to the training? Could we do deep visualization using untrained, random weight networks? To address this issue, we explore new and powerful generative models for three popular deep visualization tasks using untrained, random weight convolutional neural networks. First we invert representations in feature spaces and reconstruct images from white noise inputs. The reconstruction quality is statistically higher than that of the same method applied on well trained networks with the same architecture. Next we synthesize textures using scaled correlations of representations in multiple layers and our results are almost indistinguishable with the original natural texture and the synthesized textures based on the trained network. Third, by recasting the content of an image in the style of various artworks, we create artistic images with high perceptual quality, highly competitive to the prior work of Gatys et al. on pretrained networks. To our knowledge this is the first demonstration of image representations using untrained deep neural networks. Our work provides a new and fascinating tool to study the representation of deep network architecture and sheds light on new understandings on deep visualization. It may possibly lead to a way to compare network architectures without training.

PDF Details

NeurIPS Conference 2013 Conference Paper

Sign Cauchy Projections and Chi-Square Kernel

Ping Li
Gennady Samorodnitsk
John Hopcroft

The method of Cauchy random projections is popular for computing the $l_1$ distance in high dimension. In this paper, we propose to use only the signs of the projected data and show that the probability of collision (i. e. , when the two signs differ) can be accurately approximated as a function of the chi-square ($\chi^2$) similarity, which is a popular measure for nonnegative data (e. g. , when features are generated from histograms as common in text and vision applications). Our experiments confirm that this method of sign Cauchy random projections is promising for large-scale learning applications. Furthermore, we extend the idea to sign $\alpha$-stable random projections and derive a bound of the collision probability.

PDF Details

AIJ Journal 1988 Journal Article

The geometry of projective blending surfaces

Christoph Hoffmann
John Hopcroft

Blending surfaces smoothly join two or more primary surfaces that otherwise would intersect in edges. We outline the potential method for deriving blending surfaces, and explain why the method needs to be considered in projective parameter space, concentrating on the case of blending quadrics. Let W be the quadratic polynomial substituted for the homogenizing variable of parameter space. We show that a blending surface derived in projective parameter space is the projective image of a different blending surface derived in affine parameter space, provided that W = U2 for some linear U. All blending surfaces may therefore by classified on basis of the projective classification of W.

Details DOI

TCS Journal 1980 Journal Article

The directed subgraph homeomorphism problem

Steven Fortune
John Hopcroft
James Wyllie

The set of pattern graphs for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.

Details DOI

TCS Journal 1979 Journal Article

On the reachability problem for 5-dimensional vector addition systems

John Hopcroft
Jean-Jacques Pansiot

The reachability sets for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. Thus reachability, equivalence and containment are decidable up to dimension 5. An example of a non-semilinear reachability set is given for dimension 6.

Details DOI