Search

Recent work has explored video action recognition as a video-text matching problem and several effective methods have been proposed based on large-scale pre-trained vision-language models. However, these approaches primarily operate at a coarse-grained level without the detailed and semantic understanding of action concepts by exploiting fine-grained semantic connections between actions and body movements. To address this gap, we propose a contrastive video-language learning framework guided by a knowledge graph, termed KG-CLIP, which incorporates structured information into the CLIP model in the video domain. Specifically, we construct a multi-modal knowledge graph composed of multi-grained concepts by parsing actions based on compositional learning. By implementing a triplet encoder and deviation compensation to adaptively optimize the margin in the entity distance function, our model aims to improve alignment of entities in the knowledge graph to better suit complex relationship learning. This allows for enhanced video action recognition capabilities by accommodating nuanced associations between graph components. We comprehensively evaluate KG-CLIP on Kinetics-TPS, a large-scale action parsing dataset, demonstrating its effectiveness compared to competitive baselines. Especially, our method excels at action recognition with few sample frames or limited training data, which exhibits excellent data utilization and learning capabilities.

Video recognition remains an open challenge, requiring the identification of diverse content categories within videos. Mainstream approaches often perform flat classification, overlooking the intrinsic hierarchical structure relating categories. To address this, we formalize the novel task of hierarchical video recognition, and propose a video-language learning framework tailored for hierarchical recognition. Specifically, our framework encodes dependencies between hierarchical category levels, and applies a top-down constraint to filter recognition predictions. We further construct a new fine-grained dataset based on medical assessments for rehabilitation of stroke patients, serving as a challenging benchmark for hierarchical recognition. Through extensive experiments, we demonstrate the efficacy of our approach for hierarchical recognition, significantly outperforming conventional methods, especially for fine-grained subcategories. The proposed framework paves the way for hierarchical modeling in video understanding tasks, moving beyond flat categorization.

Vertical Federated Learning (VFL), which has a broad range of real-world applications, has received much attention in both academia and industry. Enterprises aspire to exploit more valuable features of the same users from diverse departments to boost their model prediction skills. VFL addresses this demand and concurrently secures individual parties from exposing their raw data. However, conventional VFL encounters a bottleneck as it only leverages aligned samples, whose size shrinks with more parties involved, resulting in data scarcity and the waste of unaligned data. To address this problem, we propose a novel VFL Hybrid Local Pre-training (VFLHLP) approach. VFLHLP first pre-trains local networks on the local data of participating parties. Then it utilizes these pre-trained networks to adjust the sub-model for the labeled party or enhance representation learning for other parties during downstream federated learning on aligned data, boosting the performance of federated models. The experimental results on real-world advertising datasets, demonstrate that our approach achieves the best performance over baseline methods by large margins. The ablation study further illustrates the contribution of each technique in VFLHLP to its overall performance.

Astronomical knowledge entities, such as celestial object identifiers, are crucial for literature retrieval and knowledge graph construction, and other research and applications in the field of astronomy. Traditional methods of extracting knowledge entities from texts face challenges like high manual effort, poor generalization, and costly maintenance. Consequently, there is a pressing need for improved methods to efficiently extract them. This study explores the potential of pre-trained Large Language Models (LLMs) to perform astronomical knowledge entity extraction (KEE) task from astrophysical journal articles using prompts. We propose a prompting strategy called Prompt-KEE, which includes five prompt elements, and design eight combination prompts based on them. Celestial object identifier and telescope name, two most typical astronomical knowledge entities, are selected to be experimental object. And we introduce four currently representative LLMs, namely Llama-2-70B, GPT-3.5, GPT-4, and Claude 2. To accommodate their token limitations, we construct two datasets: the full texts and paragraph collections of 30 articles. Leveraging the eight prompts, we test on full texts with GPT-4 and Claude 2, on paragraph collections with all LLMs. The experimental results demonstrated that pre-trained LLMs have the significant potential to perform KEE tasks in astrophysics journal articles, but there are differences in their performance. Furthermore, we analyze some important factors that influence the performance of LLMs in entity extraction and provide insights for future KEE tasks in astrophysical articles using LLMs.

The development of Internet technology enables an analysis on the whole population rather than a certain number of samples, and leads to increasing requirement for privacy protection. Local differential privacy (LDP) is an effective standard of privacy measurement; however, its large variance of mean estimation causes challenges in application. To address this problem, this paper presents a new LDP approach, an improved Christofides mechanism. It compared four statistical survey methods for conducting surveys on sensitive topics -- modified Warner, Simmons, Christofides, and the improved Christofides mechanism. Specifically, Warner, Simmons and Christofides mechanisms have been modified to draw a sample from the population without replacement, to decrease variance. Furthermore, by drawing cards without replacement based on modified Christofides mechanism, we introduce a new mechanism called the improved Christofides mechanism, which is found to have the smallest variance under certain assumption when using LDP as a measurement of privacy leakage. The assumption is do satisfied usually in the real world. Actually, we decrease the variance to 28.7% of modified Christofides mechanism's variance in our experiment based on the HCOVANY dataset -- a real world dataset of IPUMS USA. This means our method gets a more accurate estimate by using LDP as a measurement of privacy leakage. This is the first time the improved Christofides mechanism is proposed for LDP framework based on comparative analysis of four mechanisms using LDP as the same measurement of privacy leakage.

The Yarkovsky-O'Keefe-Radzievskii-Paddack (YORP) effect plays an important role in the rotational properties and evolution of asteroids. While the YORP effect induced by the macroscopic shape of the asteroid and by the presence of surface boulders has been well studied, no investigation has been performed yet regarding how craters with given properties influence this effect. We introduce and estimate the crater-induced YORP effect (CYORP), which arises from the concave structure of the crater, to investigate the magnitude of the resulting torques as a function of varying properties of the crater and the asteroid by a semi-analytical method. The CYORP torque can be comparable to the normal YORP torque when the size of the crater is about one-tenth of the size of the asteroid, or equivalently when the crater/roughness covers one-tenth of the asteroid's surface. Although the torque decreases with the crater size, the combined contribution of all small craters can become non-negligible due to their large number when the commonly used power-law crater size distribution is considered. The CYORP torque of small concave structures, usually considered as surface roughness, is essential to the accurate calculation of the complete YORP torque. Under the CYORP effect that is produced by collisions, asteroids go through a random walk in spin rate and obliquity, with a YORP reset timescale typically of 0.4 Myr. This has strong implications for the rotational evolution and orbital evolution of asteroids. Craters and roughness on asteroid surfaces can influence the YORP torques and therefore the rotational properties and evolution of asteroids. We suggest that the CYORP effect should be considered in the future investigation of the YORP effect on asteroids., Comment: 13 pages, 7 figures. Accepted by A&A

Data privacy is an essential issue in publishing data visualizations. However, it is challenging to represent multiple data patterns in privacy-preserving visualizations. The prior approaches target specific chart types or perform an anonymization model uniformly without considering the importance of data patterns in visualizations. In this paper, we propose a visual analytics approach that facilitates data custodians to generate multiple private charts while maintaining user-preferred patterns. To this end, we introduce pattern constraints to model users' preferences over data patterns in the dataset and incorporate them into the proposed Bayesian network-based Differential Privacy (DP) model PriVis. A prototype system, DPVisCreator, is developed to assist data custodians in implementing our approach. The effectiveness of our approach is demonstrated with quantitative evaluation of pattern utility under the different levels of privacy protection, case studies, and semi-structured expert interviews., Comment: 9 pages, 5 figures

In the age of social computing, finding interesting network patterns or motifs is significant and critical for various areas such as decision intelligence, intrusion detection, medical diagnosis, social network analysis, fake news identification, national security, etc. However, sub-graph matching remains a computationally challenging problem, let alone identifying special motifs among them. This is especially the case in large heterogeneous real-world networks. In this work, we propose an efficient solution for discovering and ranking human behavior patterns based on network motifs by exploring a user's query in an intelligent way. Our method takes advantage of the semantics provided by a user's query, which in turn provides the mathematical constraint that is crucial for faster detection. We propose an approach to generate query conditions based on the user's query. In particular, we use meta paths between nodes to define target patterns as well as their similarities, leading to efficient motif discovery and ranking at the same time. The proposed method is examined on a real-world academic network, using different similarity measures between the nodes. The experiment result demonstrates that our method can identify interesting motifs, and is robust to the choice of similarity measures.

Climate system teleconnections are crucial for improving climate predictability, but difficult to quantify. Standard approaches to identify teleconnections are often based on correlations between time series. Here we present a novel method leveraging Granger causality, which can infer/detect relationships between any two fields. We compare teleconnections identified by correlation and Granger causality at different timescales. We find that both Granger causality and correlation consistently recover known seasonal precipitation responses to the sea surface temperature pattern associated with the El Ni\~{n}o Southern Oscillation. Such findings are robust across multiple time resolutions. In addition, we identify candidates for unexplored teleconnection responses., Comment: 13 pages, 11 figures, code can be found in https://github.com/filipinascimento/teleconnectionsgranger

We propose a information theoretical framework to capture transition and information costs of network navigation models. Based on the minimum description length principle and the Markov decision process, we demonstrate that efficient global navigation can be achieved with only partial information. Additionally, we derived a scalable algorithm for optimal solutions under certain conditions. The proposed algorithm can be interpreted as a dynamical process on network, making it a useful tool for analysing and understanding navigation strategies on real world networks., Comment: To appear in the Proceedings of the 2020 IEEE International Conference on Networking, Sensing and Control (ICNSC2020)

This paper analyzes the impact of air transport connectivity and accessibility on scientific collaboration., Comment: 3 figures, 7 tables

Weight thresholding is a simple technique that aims at reducing the number of edges in weighted networks that are otherwise too dense for the application of standard graph theoretical methods. We show that the group structure of real weighted networks is very robust under weight thresholding, as it is maintained even when most of the edges are removed. This appears to be related to the correlation between topology and weight that characterizes real networks. On the other hand, the behavior of other properties is generally system dependent., Comment: To appear in Physical Review E

Communication of signals among nodes in a complex network poses fundamental problems of efficiency and cost. Routing of messages along shortest paths requires global information about the topology, while spreading by diffusion, which operates according to local topological features, is informationally "cheap" but inefficient. We introduce a stochastic model for network communication that combines varying amounts of local and global information about the network topology. The model generates a continuous spectrum of dynamics that converge onto shortest-path and random-walk (diffusion) communication processes at the limiting extremes. We implement the model on two cohorts of human connectome networks and investigate the effects of varying amounts of local and global information on the network's communication cost. We identify routing strategies that approach a (highly efficient) shortest-path communication process with a relatively small amount of global information. Moreover, we show that the cost of routing messages from and to hub nodes varies as a function of the amount of global information driving the system's dynamics. Finally, we implement the model to identify individual subject differences from a communication dynamics point of view. The present framework departs from the classical shortest paths vs. diffusion dichotomy, suggesting instead that brain networks may exhibit different types of communication dynamics depending on varying functional demands and the availability of resources.

In network science, the interplay between dynamical processes and the underlying topologies of complex systems has led to a diverse family of models with different interpretations. In graph signal processing, this is manifested in the form of different graph shifts and their induced algebraic systems. In this paper, we propose the unifying Z-Laplacian framework, whose instances can act as graph shift operators. As a generalization of the traditional graph Laplacian, the Z-Laplacian spans the space of all possible Z-matrices, i.e., real square matrices with nonpositive off-diagonal entries. We show that the Z-Laplacian can model general continuous-time dynamical processes, including information flows and epidemic spreading on a given graph. It is also closely related to general nonnegative graph filters in the discrete time domain. We showcase its flexibility by considering two applications. First, we consider a wireless communications networking problem modeled with a graph, where the framework can be applied to model the effects of the underlying communications protocol and traffic. Second, we examine a structural brain network from the perspective of low- to high-frequency connectivity., Comment: IEEE Journal of Selected Topics in Signal Processing (September 2017 special issue on Graph Signal Processing)

It is common for people to access multiple social networks, for example, using phone, email, and social media. Together, the multi-layer social interactions form a "integrated social network." How can we extend well developed knowledge about single-layer networks, including vertex centrality and community structure, to such heterogeneous structures? In this paper, we approach these challenges by proposing a principled framework of network composition based on a unified dynamical process. Mathematically, we consider the following abstract problem: Given multi-layer network data and additional parameters for intra and inter-layer dynamics, construct a (single) weighted network that best integrates the joint process. We use transformations of dynamics to unify heterogeneous layers under a common dynamics. For inter-layer compositions, we will consider several cases as the inter-layer dynamics plays different roles in various social or technological networks. Empirically, we provide examples to highlight the usefulness of this framework for network analysis and network design.

A central problem in analyzing networks is partitioning them into modules or communities. One of the best tools for this is the stochastic block model, which clusters vertices into blocks with statistically homogeneous pattern of links. Despite its flexibility and popularity, there has been a lack of principled statistical model selection criteria for the stochastic block model. Here we propose a Bayesian framework for choosing the number of blocks as well as comparing it to the more elaborate degree- corrected block models, ultimately leading to a universal model selection framework capable of comparing multiple modeling combinations. We will also investigate its connection to the minimum description length principle.

Social behaviors are often contagious, spreading through a population as individuals imitate the decisions and choices of others. A variety of global phenomena, from innovation adoption to the emergence of social norms and political movements, arise as a result of people following a simple local rule, such as copy what others are doing. However, individuals often lack global knowledge of the behaviors of others and must estimate them from the observations of their friends' behaviors. In some cases, the structure of the underlying social network can dramatically skew an individual's local observations, making a behavior appear far more common locally than it is globally. We trace the origins of this phenomenon, which we call "the majority illusion," to the friendship paradox in social networks. As a result of this paradox, a behavior that is globally rare may be systematically overrepresented in the local neighborhoods of many people, i.e., among their friends. Thus, the "majority illusion" may facilitate the spread of social contagions in networks and also explain why systematic biases in social perceptions, for example, of risky behavior, arise. Using synthetic and real-world networks, we explore how the "majority illusion" depends on network structure and develop a statistical model to calculate its magnitude in a network.

The structure of real-world social networks in large part determines the evolution of social phenomena, including opinion formation, diffusion of information and influence, and the spread of disease. Globally, network structure is characterized by features such as degree distribution, degree assortativity, and clustering coefficient. However, information about global structure is usually not available to each vertex. Instead, each vertex's knowledge is generally limited to the locally observable portion of the network consisting of the subgraph over its immediate neighbors. Such subgraphs, known as ego networks, have properties that can differ substantially from those of the global network. In this paper, we study the structural properties of ego networks and show how they relate to the global properties of networks from which they are derived. Through empirical comparisons and mathematical derivations, we show that structural features, similar to static attributes, suffer from paradoxes. We quantify the differences between global information about network structure and local estimates. This knowledge allows us to better identify and correct the biases arising from incomplete local information., Comment: Accepted by SBP 2015, to appear in the proceedings

We study the interplay between a dynamic process and the structure of the network on which it is defined. Specifically, we examine the impact of this interaction on the quality-measure of network clusters and node centrality. This enables us to effectively identify network communities and important nodes participating in the dynamics. As the first step towards this objective, we introduce an umbrella framework for defining and characterizing an ensemble of dynamic processes on a network. This framework generalizes the traditional Laplacian framework to continuous-time biased random walks and also allows us to model some epidemic processes over a network. For each dynamic process in our framework, we can define a function that measures the quality of every subset of nodes as a potential cluster (or community) with respect to this process on a given network. This subset-quality function generalizes the traditional conductance measure for graph partitioning. We partially justify our choice of the quality function by showing that the classic Cheeger's inequality, which relates the conductance of the best cluster in a network with a spectral quantity of its Laplacian matrix, can be extended from the Laplacian-conductance setting to this more general setting., Comment: This is the full length version. A shorter conference paper appeared in ACM-SIGKDD 2014

Many data sets contain rich information about objects, as well as pairwise relations between them. For instance, in networks of websites, scientific papers, and other documents, each node has content consisting of a collection of words, as well as hyperlinks or citations to other nodes. In order to perform inference on such data sets, and make predictions and recommendations, it is useful to have models that are able to capture the processes which generate the text at each node and the links between them. In this paper, we combine classic ideas in topic modeling with a variant of the mixed-membership block model recently developed in the statistical physics community. The resulting model has the advantage that its parameters, including the mixture of topics of each document and the resulting overlapping communities, can be inferred with a simple and scalable expectation-maximization algorithm. We test our model on three data sets, performing unsupervised topic classification and link prediction. For both tasks, our model outperforms several existing state-of-the-art methods, achieving higher accuracy with significantly less computation, analyzing a data set with 1.3 million words and 44 thousand links in a few minutes., Comment: 11 pages, 4 figures

The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks. We illustrate these challenges, and show one way to resolve them, by considering the key network-analysis problem of dividing a graph into communities or blocks of nodes with homogeneous patterns of links to the rest of the network. The standard tool for doing this is the stochastic block model, under which the probability of a link between two nodes is a function solely of the blocks to which they belong. This imposes a homogeneous degree distribution within each block; this can be unrealistic, so degree-corrected block models add a parameter for each node, modulating its over-all degree. The choice between ordinary and degree-corrected block models matters because they make very different inferences about communities. We present the first principled and tractable approach to model selection between standard and degree-corrected block models, based on new large-graph asymptotics for the distribution of log-likelihood ratios under the stochastic block model, finding substantial departures from classical results for sparse graphs. We also develop linear-time approximations for log-likelihoods under both the stochastic block model and the degree-corrected model, using belief propagation. Applications to simulated and real networks show excellent agreement with our approximations. Our results thus both solve the practical problem of deciding on degree correction, and point to a general approach to model selection in network analysis.

The stochastic block model is a powerful tool for inferring community structure from network topology. However, it predicts a Poisson degree distribution within each community, while most real-world networks have a heavy-tailed degree distribution. The degree-corrected block model can accommodate arbitrary degree distributions within communities. But since it takes the vertex degrees as parameters rather than generating them, it cannot use them to help it classify the vertices, and its natural generalization to directed graphs cannot even use the orientations of the edges. In this paper, we present variants of the block model with the best of both worlds: they can use vertex degrees and edge orientations in the classification process, while tolerating heavy-tailed degree distributions within communities. We show that for some networks, including synthetic networks and networks of word adjacencies in English text, these new block models achieve a higher accuracy than either standard or degree-corrected block models., Comment: 22 pages, 3 figures

In many real-world networks, nodes have class labels, attributes, or variables that affect the network's topology. If the topology of the network is known but the labels of the nodes are hidden, we would like to select a small subset of nodes such that, if we knew their labels, we could accurately predict the labels of all the other nodes. We develop an active learning algorithm for this problem which uses information-theoretic techniques to choose which nodes to explore. We test our algorithm on networks from three different domains: a social network, a network of English words that appear adjacently in a novel, and a marine food web. Our algorithm makes no initial assumptions about how the groups connect, and performs well even when faced with quite general types of network structure. In particular, we do not assume that nodes of the same class are more likely to be connected to each other---only that they connect to the rest of the network in similar ways., Comment: 9 pages, 7 figures, KDD 2011: The 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

In many networks, vertices have hidden attributes, or types, that are correlated with the networks topology. If the topology is known but these attributes are not, and if learning the attributes is costly, we need a method for choosing which vertex to query in order to learn as much as possible about the attributes of the other vertices. We assume the network is generated by a stochastic block model, but we make no assumptions about its assortativity or disassortativity. We choose which vertex to query using two methods: 1) maximizing the mutual information between its attributes and those of the others (a well-known approach in active learning) and 2) maximizing the average agreement between two independent samples of the conditional Gibbs distribution. Experimental results show that both these methods do much better than simple heuristics. They also consistently identify certain vertices as important by querying them early on.