MQMiao Qiao

Miao Qiao

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Miao Qiao has a total of 63 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    LSHAlign: All-Pair Near-Duplicate Text Alignment via Locality-Sensitive Hashing

    by Yuheng Zhang, Zhencan Peng, Miao Qiao, Wei Zhang, Feifei Li, Dong Deng

    The all-pair near-duplicate text alignment problem aims to identify all pairs of similar subsequences (i.e., contiguous token spans) between two long texts. This problem is central to many applications, including large-scale text deduplication, plagiarism detection, and bioinformatics. Given two input texts T and S, each represented as a sequence of tokens, the naive approach that compares every pair of subsequences between T and S is computationally infeasible, requiring O (|T| 2 |S| 2 k ) time even when estimating Jaccard similarity via min-hash with k independent hash functions. To overcome this limitation, we propose an efficient framework based on Locality-Sensitive Hashing (LSH), which employs m × L independent hash functions organized into L hash tables of m hash functions each. Our key observation is that many subsequences in a text share identical LSH values, allowing us to group them by their LSH values. We prove that the expected number of such groups for a text of length n is O ( nmL ). We further design a data structure to represent each group in O (1) space. As a result, we develop an algorithm that reduces the expected time and space complexities of all-pair near-duplicate text alignment to O ((|T|+|S|) mL ), excluding the cost of outputting the pairs. This is significantly lower than the naive approach using the same number k = m × L of hash functions. Experiments on large real-world datasets show an order of magnitude speedups over state-of-the-art baselines while maintaining comparable alignment accuracy.

  • Open Access

    MaCTG: Multi-Agent Collaborative Thought Graph for Automatic Programming

    by Zixiao Zhao, Jing Sun, Zhe Hou, Zhiyuan Wei, Cheng-Hao Cai, Miao Qiao, Jin Song Dong

  • Open Access

    Scaling Up k-Clique Percolation Community Detection

    by Yue Zeng, Miao Qiao, Rong-Hua Li, Hongchao Qin, Guoren Wang

    Overlapping communities are pervasive in real-world networks, where vertices often participate in multiple communities simultaneously. The k -clique percolation community (KCPC) model represents a fundamental paradigm for mining overlapping communities. However, existing KCPC mining methods are often hampered by inefficiency and scalability challenges, hindering their applicability to large-scale networks. To address these challenges, we propose several novel and efficient approaches for KCPC mining from perspectives of maximal cliques and k -cliques. Specifically, we first present a novel concept, termed Quasi-KCPC, which represents an incomplete KCPC and can be efficiently obtained as a byproduct during the maximal clique enumeration procedure. Based on Quasi-KCPC, we first propose a maximal clique enumeration-based solution that builds upon existing maximal clique adjacency graph traversal methods, but achieves improved efficiency by using Quasi-KCPC to dramatically reduce the scale of the maximal clique adjacency graph. Additionally, we propose a novel k -clique listing-based solution, which adopts a different strategy: it first enumerates (k-1)-cliques and then connects the k -cliques sharing these (k-1)-cliques into KCPC. Our method further improves efficiency by shifting the connection target from k -cliques to maximal cliques and employing Quasi-KCPC to significantly prune the k -clique enumeration tree. We also propose update algorithms for KCPC to handle dynamic addition and deletion of vertices and edges, enabling real-time analysis of KCPC. Extensive experiments on 12 large real-world graphs demonstrate the superiority of our algorithms, which can be up to two orders of magnitude faster than existing state-of-the-art solutions in KCPC mining, and almost two orders of magnitude faster than recomputation strategy in dynamic KCPC updates.

  • Open Access

    $α$-GAN by Rényi Cross Entropy

    by Ni Ding, Miao Qiao, Jiaxing Xu, Yiping Ke, Xiaoyu Zhang

    This paper proposes $α$-GAN, a generative adversarial network using Rényi measures. The value function is formulated, by Rényi cross entropy, as an expected certainty measure incurred by the discriminator's soft decision as to where the sample is from, true population or the generator. The discriminator tries to maximize the Rényi certainty about sample source, while the generator wants to reduce it by injecting fake samples. This forms a min-max problem with the solution parameterized by the Rényi order $α$. This $α$-GAN reduces to vanilla GAN at $α= 1$, where the value function is exactly the binary cross entropy. The optimization of $α$-GAN is over probability (vector) space. It is shown that the gradient is exponentially enlarged when Rényi order is in the range $α\in (0,1)$. This makes convergence faster, which is verified by experimental results. A discussion shows that choosing $α\in (0,1)$ may be able to solve some common problems, e.g., vanishing gradient. A following observation reveals that this range has not been fully explored in the existing Rényi version GANs.

  • Open Access

    On Graph Representation for Attributed Hypergraph Clustering

    by Zijin Feng, Miao Qiao, Chengzhi Piao, Hong Cheng

    Attributed Hypergraph Clustering (AHC) aims at partitioning a hypergraph into clusters such that nodes in the same cluster are close to each other with both high connectedness and homogeneous attributes. Existing AHC methods are all based on matrix factorization which may incur a substantial computation cost; more importantly, they inherently require a prior knowledge of the number of clusters as an input which, if inaccurately estimated, shall lead to a significant deterioration in the clustering quality. In this paper, we propose Attributed Hypergraph Representation for Clustering (AHRC), a cluster-number-free hypergraph clustering consisting of an effective integration of the hypergraph topology and node attributes for hypergraph representation, a multi-hop modularity function for optimization, and a hypergraph sparsification for scalable computation. AHRC achieves cutting-edge clustering quality and efficiency: compared to the state-of-the-art (SOTA) AHC method on 10 real hypergraphs, AHRC obtains an average of 20% higher F-measure, 24% higher ARI, 26% higher Jaccard Similarity, 10% higher Purity, and runs 5.5× faster. As a byproduct, the intermediate result of graph representation dramatically boosts the clustering quality of SOTA contrastive-learning-based hypergraph clustering methods, showing the generality of our graph representation.


  • Open Access

    Contrasformer: A Brain Network Contrastive Transformer for Neurodegenerative Condition Identification

    by Jiaxing Xu, Kai He, Mengcheng Lan, Qingtian Bian, Wei Li, Tieying Li, Yiping Ke, Miao Qiao

    Understanding neurological disorder is a fundamental problem in neuroscience, which often requires the analysis of brain networks derived from functional magnetic resonance imaging (fMRI) data. Despite the prevalence of Graph Neural Networks (GNNs) and Graph Transformers in various domains, applying them to brain networks faces challenges. Specifically, the datasets are severely impacted by the noises caused by distribution shifts across sub-populations and the neglect of node identities, both obstruct the identification of disease-specific patterns. To tackle these challenges, we propose Contrasformer, a novel contrastive brain network Transformer. It generates a prior-knowledge-enhanced contrast graph to address the distribution shifts across sub-populations by a two-stream attention mechanism. A cross attention with identity embedding highlights the identity of nodes, and three auxiliary losses ensure group consistency. Evaluated on 4 functional brain network datasets over 4 different diseases, Contrasformer outperforms the state-of-the-art methods for brain networks by achieving up to 10.8% improvement in accuracy, which demonstrates its efficacy in neurological disorder identification. Case studies illustrate its interpretability, especially in the context of neuroscience. This paper provides a solution for analyzing brain networks, offering valuable insights into neurological disorders. Our code is available at https://github.com/AngusMonroe/Contrasformer.


  • Open Access

    On Density-based Local Community Search

    by Yizhou Dai, Miao Qiao, Rong-Hua Li

    Local community search (LCS) finds a community in a given graph G local to a set R of seed nodes by optimizing an objective function. The objective function f(S) for an induced subgraph S encodes the set inclusion criteria of R to a classic community measurement of S such as the conductance and the density. An ideal algorithm for optimizing f(S) is strongly local, that is, the complexity is dependent on R as opposed to G. This paper formulates a general form of objective functions for LCS using configurations and then focuses on a set C of density-based configurations, each corresponding to a density-based LCS objective function. The paper has two main results. i) A constructive classification of C: a configuration in C has a strongly local algorithm for optimizing its corresponding objective function if and only if it is in C L ⊆ C. ii) A linear programming-based general solution for density-based LCS that is strongly local and practically efficient. This solution is different from the existing strongly local LCS algorithms, which are all based on flow networks.


  • Top Cited Papers
    Open Access

    SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search

    by Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, Dong Deng

    Effective vector representation models, e.g., word2vec and node2vec, embed real-world objects such as images and documents in high dimensional vector space. In the meanwhile, the objects are often associated with attributes such as timestamps and prices. Many scenarios need to jointly query the vector representations of the objects together with their attributes. These queries can be formalized as range-filtering approximate nearest neighbor search (ANNS) queries. Specifically, given a collection of data vectors, each associated with an attribute value whose domain has a total order. The range-filtering ANNS consists of a query range and a query vector. It finds the approximate nearest neighbors of the query vector among all the data vectors whose attribute values fall in the query range. Existing approaches suffer from a rapidly degrading query performance when the query range width shifts. The query performance can be optimized by a solution that builds an ANNS index for every possible query range; however, the index time and index size become prohibitive -- the number of query ranges is quadratic to the number n of data vectors. To overcome these challenges, for the query range contains all attribute values smaller than a user-provided threshold, we design a structure called the segment graph whose index time and size are the same as a single ANNS index, yet can losslessly compress the n ANNS indexes, reducing the indexing cost by a factor of Ω(n). To handle general range queries, we propose a 2D segment graph with average-case index size O(n log n) to compress n segment graphs, breaking the quadratic barrier. Extensive experiments conducted on real-world datasets show that our proposed structures outperformed existing methods significantly; our index also exhibits superior scalability.


  • Open Access

    Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation

    by Zijin Feng, Miao Qiao, Hong Cheng

    A graph models the connections among objects. One important graph analytical task is clustering which partitions a data graph into clusters with dense innercluster connections. A line of clustering maximizes a function called modularity. Modularity-based clustering is widely adopted on dyadic graphs due to its scalability and clustering quality which depends highly on its selection of a random graph model. The random graph model decides not only which clustering is preferred - modularity measures the quality of a clustering based on its alignment to the edges of a random graph, but also the cost of computing such an alignment. Existing random hypergraph models either measure the hyperedge-cluster alignment in an All-Or-Nothing (AON) manner, losing important group-wise information, or introduce expensive alignment computation, refraining the clustering from scaling up. This paper proposes a new random hypergraph model called Hyperedge Expansion Model (HEM), a non-AON hypergraph modularity function called Partial Innerclusteredge modularity (PI) based on HEM, a clustering algorithm called Partial Innerclusteredge Clustering (PIC) that optimizes PI, and novel computation optimizations. PIC is a scalable modularity-based hypergraph clustering that can effectively capture the non-AON hyperedge-cluster relation. Our experiments show that PIC outperforms eight state-of-the-art methods on real-world hypergraphs in terms of both clustering quality and scalability and is up to five orders of magnitude faster than the baseline methods.


  • Open Access

    Centralization Problem for Opinion Convergence in Decentralized Networks

    by Yiping Liu, Jiamou Liu, Bakh Khoussainov, Miao Qiao, Bo Yan, Mengxiao Zhang