Search

Community detection (CD) is a classic graph inference task that partitions nodes of a graph into densely connected groups. While many CD methods have been proposed with either impressive quality or efficiency, balancing the two aspects remains a challenge. This study explores the potential of deep graph learning to achieve a better trade-off between the quality and efficiency of K-agnostic CD, where the number of communities K is unknown. We propose PRoCD (Pre-training & Refinement fOr Community Detection), a simple yet effective method that reformulates K-agnostic CD as the binary node pair classification. PRoCD follows a pre-training & refinement paradigm inspired by recent advances in pre-training techniques. We first conduct the offline pre-training of PRoCD on small synthetic graphs covering various topology properties. Based on the inductive inference across graphs, we then generalize the pre-trained model (with frozen parameters) to large real graphs and use the derived CD results as the initialization of an existing efficient CD method (e.g., InfoMap) to further refine the quality of CD results. In addition to benefiting from the transfer ability regarding quality, the online generalization and refinement can also help achieve high inference efficiency, since there is no time-consuming model optimization. Experiments on public datasets with various scales demonstrate that PRoCD can ensure higher efficiency in K-agnostic CD without significant quality degradation., Comment: Accepted by ACM KDD 2024

Graph partitioning (GP), a.k.a. community detection, is a classic problem that divides the node set of a graph into densely-connected blocks. Following prior work on the IEEE HPEC Graph Challenge benchmark and recent advances in graph machine learning, we propose a novel RAndom FasT Graph Partitioning (RaftGP) method based on an efficient graph embedding scheme. It uses the Gaussian random projection to extract community-preserving features from classic GP objectives. These features are fed into a graph neural network (GNN) to derive low-dimensional node embeddings. Surprisingly, our experiments demonstrate that a randomly initialized GNN even without training is enough for RaftGP to derive informative community-preserving embeddings and support high-quality GP. To enable the derived embeddings to tackle GP, we introduce a hierarchical model selection algorithm that simultaneously determines the number of blocks and the corresponding GP result. We evaluate RaftGP on the Graph Challenge benchmark and compare the performance with five baselines, where our method can achieve a better trade-off between quality and efficiency. In particular, compared to the baseline algorithm of the IEEE HPEC Graph Challenge, our method is 6.68x -- 23.9x faster on graphs with 1E3 -- 5E4 nodes and at least 64.5x faster on larger (1E5 node) graphs on which the baseline takes more than 1E4 seconds. Our method achieves better accuracy on all test cases. We also develop a new graph generator to address some limitations of the original generator in the benchmark.

A powerful technique for solving combinatorial optimization problems is to reduce the search space without compromising the solution quality by exploring intrinsic mathematical properties of the problems. For the maximum weight independent set (MWIS) problem, using an upper bound lemma which says the weight of any independent set not contained in the MWIS is bounded from above by the weight of the intersection of its closed neighbor set and the MWIS, we give two extension theorems -- independent set extension theorem and vertex cover extension theorem. With them at our disposal, two types of causal inference techniques (CITs) are proposed on the assumption that a vertex is strongly reducible (included or not included in all MWISs) or reducible (contained or not contained in a MWIS). One is a strongly reducible state-preserving technique, which extends a strongly reducible vertex into a vertex set where all vertices have the same strong reducibility. The other, as a reducible state-preserving technique, extends a reducible vertex into a vertex set with the same reducibility as that vertex and creates some weighted packing constraints to narrow the search space. Numerical experiments show that our CITs can help reduction algorithms find much smaller remaining graphs, improve the ability of exact algorithms to find the optimal solutions and help heuristic algorithms produce approximate solutions of better quality. In particular, detailed tests on $12$ representative graphs generated from datasets in Network Data Repository demonstrate that, compared to the state-of-the-art algorithms, the size of remaining graphs is further reduced by more than 32.6%, and the number of solvable instances is increased from 1 to 5., Comment: 31 pages, 5 figures, submitted for publication on Jan. 13, 2023

Capacity constrained optimal transport is a variant of optimal transport, which adds extra constraints on the set of feasible couplings in the original optimal transport problem to limit the mass transported between each pair of source and sink. Based on this setting, constrained optimal transport has numerous applications, e.g., finance, network flow. However, due to the large number of constraints in this problem, existing algorithms are both time-consuming and space-consuming. In this paper, inspired by entropic regularization for the classical optimal transport problem, we introduce a novel regularization term for capacity constrained optimal transport. The regularized problem naturally satisfies the capacity constraints and consequently makes it possible to analyze the duality. Unlike the matrix-vector multiplication in the alternate iteration scheme for solving classical optimal transport, in our algorithm, each alternate iteration step is to solve several single-variable equations. Fortunately, we find that each of these equations corresponds to a single-variable monotonic function, and we convert solving these equations into finding the unique zero point of each single-variable monotonic function with Newton's method. Extensive numerical experiments demonstrate that our proposed method has a significant advantage in terms of accuracy, efficiency, and memory consumption compared with existing methods., Comment: 17 pages, 3 figures

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD). Due to the NP-hardness, to balance the CD quality and efficiency remains a challenge. Most existing CD methods are transductive, which are independently optimized only for the CD on a single graph. Some of these methods use advanced machine learning techniques to obtain high-quality CD results but usually have high complexity. Other approaches use fast heuristic approximation to ensure low runtime but may suffer from quality degradation. In contrast to these transductive methods, we propose an alternative inductive community detection (ICD) method across graphs of a system or scenario to alleviate the NP-hard challenge. ICD first conducts the offline training of an adversarial dual GNN on historical graphs to capture key properties of the system. The trained model is then directly generalized to new unseen graphs for online CD without additional optimization, where a better trade-off between quality and efficiency can be achieved. ICD can also capture the permutation invariant community labels in the offline training and tackle the online CD on new graphs with non-fixed number of nodes and communities. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant trade-off between quality and efficiency over various baselines.

In order to increase the efficiency of phase retrieval,Wang proposed a high-speed moire phase retrieval method.But it is used only to measure the tiny object. In view of the limitation of Wang method,we proposed a dynamic three-dimensional (3D) measurement based on the phase-shifting moire algorithm.First, four sinusoidal fringe patterns with a pi/2 phase-shift are projected on the reference plane and acquired four deformed fringe patterns of the reference plane in advance. Then only single-shot deformed fringe pattern of the tested object is captured in measurement process.Four moire fringe patterns can be obtained by numerical multiplication between the the AC component of the object pattern and the AC components of the reference patterns respectively. The four low-frequency components corresponding to the moire fringe patterns are calculated by the complex encoding FT (Fourier transform) ,spectrum filtering and inverse FT.Thus the wrapped phase of the object can be determined in the tangent form from the four phase-shifting moire fringe patterns using the four-step phase shifting algorithm.The continuous phase distribution can be obtained by the conventional unwrapping algorithm. Finally, experiments were conducted to prove the validity and feasibility of the proposed method. The results are analyzed and compared with those of Wang method, demonstrating that our method not only can expand the measurement scope, but also can improve accuracy., Comment: 14 pages,5 figures. ams.org

We comment on the recent Letter by Xu and Wang et al. [Opt. Lett. 41, 2430 (2016)] in which an approach of quantitative phase extraction in dual-wavelength in-line phase-shifting interferometry (DWILPSI) was proposed. It is noted that a special phase shift is used, which more or less embarrasses its practical operation. We wish to show that the same result can also be reached by combining the generalized phase-shifting algorithm and the least-square algorithm, in which the phase shift can be chosen randomly. In addition to maintaining high accuracy and rapid processing speed of the DWILPSI method, the proposed method greatly facilitates its application in actual measurement.

It is a challenge for Phase Measurement Profilometry (PMP) to measure objects with a large range of reflectivity variation across the surface. Saturated or dark pixels in the deformed fringe patterns captured by the camera will lead to phase fluctuations and errors. Jiang et al. proposed a high dynamic range real-time 3D shape measurement method without changing camera exposures. Three inverted phase-shifted fringe patterns are used to complement three regular phase-shifted fringe patterns for phase retrieval when any of the regular fringe patterns are saturated. But Jiang's method still has some drawbacks: (1) The phases in saturated pixels are respectively estimated by different formulas for different cases. It is shortage of an universal formula; (2) it cannot be extended to four-step phase-shifting algorithm because inverted fringe patterns are the repetition of regular fringe patterns; (3) only three unsaturated intensity values at every pixel of fringe patterns are chosen for phase demodulation, lying idle the other unsaturated ones. We proposed a method for enhanced high dynamic range 3D shape measurement based on generalized phase-shifting algorithm, which combines the complementary technique of inverted and regular fringe patterns with generalized phase-shifting algorithm. Firstly, two sets of complementary phase-shifted fringe patterns, namely regular and inverted fringe patterns are projected and collected. Then all unsaturated intensity values at the same camera pixel from two sets of fringe patterns are selected, and employed to retrieve the phase by generalized phase-shifting algorithm. Finally, simulations and experiments are conducted to prove the validity of the proposed method. The results are analyzed and compared with Jiang's method, which demonstrate that the proposed method not only expands the scope of Jiang's method, but also improves the measurement accuracy., Comment: 18 pages, 22 figures