Many complex networks in the real world have community structures. Typical examples include online social networks and ecology networks. While the identification of communities bears numerous practical applications, with the increasing awareness of data security and privacy concerns, the need to protect the community affiliations of individuals from disclosing by attackers emerges. This raises the community deception (CD) problem, that is, the opposite of community detection, which asks for ways to minimally perturb the network structures by rewiring nodes so that the target communities maximally hide themself from community detection algorithms. To this end, we investigate the CD problem through a Laplacian spectrum lens and propose a method named$\mathtt {ComDeceptor}$to hide a flexible target set of communities, which is more universal than most existing methods that either focus on hiding the entire communities or a single community. The key idea of$\mathtt {ComDeceptor}$is to first allocate the resources of perturbations fairly and effectively. By proving that hiding communities through intercommunity edge addition and intracommunity edge deletion correspond to maximizing the second smallest eigenvalue$\lambda _{2}$and minimizing the largest eigenvalue$\lambda _{n}$of the graph Laplacian, respectively,$\mathtt {ComDeceptor}$then incorporates efficient heuristics for approximately solving the problems, thus selecting the appropriate edge to perturb. Experimental results over nine real-world networks and six community detection algorithms not only demonstrate the efficiency of$\mathtt {ComDeceptor}$, but also the superior performance on obfuscating community structures over the baselines.

Graph pooling refers to the operation that maps a set of node representations into a compact form for graph-level representation learning. However, existing graph pooling methods are limited by the power of the Weisfeiler–Lehman (WL) test in the performance of graph discrimination. In addition, these methods often suffer from hard adaptability to hyper-parameters and training instability. To address these issues, we propose Hi-PART, a simple yet effective graph neural network (GNN) framework with Hi erarchical Par tition T ree (HPT). In HPT, each layer is a partition of the graph with different levels of granularities that are going toward a finer grain from top to bottom. Such an exquisite structure allows us to quantify the graph structure information contained in HPT with the aid of structural information theory. Algorithmically, by employing GNNs to summarize node features into the graph feature based on HPT’s hierarchical structure, Hi-PART is able to adequately leverage the graph structure information and provably goes beyond the power of the WL test. Due to the separation of HPT optimization from graph representation learning, Hi-PART involves the height of HPT as the only extra hyper-parameter and enjoys higher training stability. Empirical results on graph classification benchmarks validate the superior expressive power and generalization ability of Hi-PART compared with state-of-the-art graph pooling approaches.

We in this paper present TiSee, an RFID-based sensing system that supports miniature robots to perform agile tasks in everyday environments. TiSee’s unique capability is that it uses a single arbitrarily-deployed antenna to locate a target with sub-cm-level accuracy and identify its orientation to within few degrees. Compared with existing solutions which rely on either antenna arrays or multiple RFID readers, TiSee is cheap, compact, and applicable to miniature robots. The idea of TiSee is to stick an RFID tag on the robot (or its gripper) and use it as a moving “antenna” to locate the tags on the target. The core of this design is a novel technique which can build a “channel” between two commercial RFID tags. Such an inter-tag channel is proved to be highly sensitive to the change in inter-tag distance and is resistant to multipath. By leveraging this channel and the mobility of the robot, we emulate an antenna array and use it for fine-grained localization and orientation estimation. Our experiments show that TiSee achieves a median accuracy of 9.5mm and 3.1° in 3D localization and orientation estimation. TiSee brings an eye-in-hand “camera” to miniature robots, supporting them to perform agile tasks in dark, cluttered, and occluded settings.

Self-supervised graph-level representation learning has recently received considerable attention. Given varied input distributions, jointly learning graphs’ unique and common features is vital to downstream tasks. Inspired by graph contrastive learning (GCL), which targets maximizing the agreement between graph representations from different views, we propose an Ada ptive self-supervised framework, Ada-MIP, considering both M utual I nformation between views (unique features) and inter-graph P roximity (common features). Specifically, Ada-MIP learns graphs’ unique information through a learnable and probably injective augmenter, which can acquire more adaptive views compared to the augmentation strategies applied by existing GCL methods; to learn graphs’ common information, we employ graph kernels to calculate graphs’ proximity and learn graph representations among which the precomputed proximity is preserved. By sharing a global encoder, graphs’ unique and common information can be well integrated into the graph representations learned by Ada-MIP. Ada-MIP is also extendable to semi-supervised scenarios, with our experiments confirming its superior performance in both unsupervised and semi-supervised tasks.

The popularity of intelligent devices provides straightforward access to the Internet and online social networks. However, the quick and easy data updates from networks also benefit the risk spreading, such as rumor, malware, or computer viruses. To this end, this article studies the problem of source detection, which is to infer the source node out of an aftermath of a cascade, that is, the observed infected graph G N of the network at some time. Prior arts have adopted various statistical quantities such as degree, distance, or infection size to reflect the structural centrality of the source. In this article, we propose a new metric that we call the infected tree entropy (ITE), to utilize richer underlying structural features for source detection. Our idea of ITE is inspired by the conception of structural entropy [ 21 ], which demonstrated that the minimization of average bits to encode the network structures with different partitions is the principle for detecting the natural or true structures in real-world networks. Accordingly, our proposed ITE based estimator for the source tries to minimize the coding of network partitions brought by the infected tree rooted at all the potential sources, thus minimizing the structural deviation between the cascades from the potential sources and the actual infection process included in G N . On polynomially growing geometric trees, with increasing tree heterogeneity, the ITE estimator remarkably yields more reliable detection under only moderate infection sizes, and returns an asymptotically complete detection. In contrast, for regular expanding trees, we still observe guaranteed detection probability of ITE estimator even with an infinite infection size, thanks to the degree regularity property. We also algorithmically realize the ITE based detection that enjoys linear time complexity via a message-passing scheme, and further extend it to general graphs. Extensive experiments on synthetic and real datasets confirm the superiority of ITE to the baselines. For example, ITE returns an accuracy of 85%, ranking the source among the top 10%, far exceeding 55% of the classic algorithm on scale-free networks.

We in this paper present TiSee, an RFID-based sensing system that supports miniature robots to perform agile tasks in everyday environments. TiSee's unique capability is that it uses a single arbitrarily-deployed antenna to locate a target with sub-cm-level accuracy and identify its orientation to within few degrees. Compared with existing solutions which rely on either antenna arrays or multiple RFID readers, TiSee is cheap, compact, and applicable to miniature robots.