Graphs are commonly employed to model complex data and discover latent patterns and relationships between entities in the real world. Canonical graph learning models have achieved remarkable progress in modeling and inference on graph-structured data that consists of nodes connected by edges. Generally, they leverage abundant labeled data for model training and thus inevitably suffer from the label scarcity issue due to the expense and hardship of data annotation in practice. Data-efficient graph learning attempts to address the prevailing data scarcity issue in graph mining problems, of which the key idea is to transfer knowledge from the related resources to obtain the models with good generalizability to the target graph-related tasks with mere annotations. However, the generalization of the models to data-scarce scenarios is faced with challenges including 1) dealing with graph structure and structural heterogeneity to extract transferable knowledge; 2) selecting beneficial and fine-grained knowledge for effective transfer; 3) addressing the divergence across different resources to promote knowledge transfer. Motivated by the aforementioned challenges, the dissertation mainly focuses on three perspectives, i.e., knowledge extraction with graph heterogeneity, knowledge selection, and knowledge transfer. The purposed models are applied to various node classification and graph classification tasks in the low-data regimes, evaluated on a variety of datasets, and have shown their effectiveness compared with the state-of-the-art baselines.

Recent advances in large graph-based models have shown great performance in a variety of tasks, including node classification, link prediction, and influence modeling. However, these graph-based models struggle to capture high-order relations and interactions among entities effectively, leading them to underperform in many real-world scenarios. This thesis focuses on analyzing networks using hypergraphs for detection, classification, and prediction methods in social media-related problems. In particular, we study four specific applications with four proposed novel methods: detecting topic-specific influential users and tweets via hypergraphs; detecting spatiotemporal, topic-specific, influential users and tweets using hypergraphs; augmenting data in hypergraphs to mitigate class imbalance issues; and introducing a novel hypergraph convolutional network model designed for the multiclass classification of mental health advice in Arabic tweets. For the first method, existing solutions for influential user detection did not consider topics that could produce incorrect results and inadequate performance in that task. The proposed contributions of our work include: 1) Developing a hypergraph framework that detects influential users and tweets. 2) Proposing an effective topic modeling method for short texts. 3) Performing extensive experiments to demonstrate the efficacy of our proposed framework. For the second method, we extend the first method by incorporating spatiotemporal information into our solution. Existing influencer detection methods do not consider spatiotemporal influencers in social media, although influence can be greatly affected by geolocation and time. The contributions of our work for this task include: 1) Proposing a hypergraph framework that spatiotemporally detects influential users and tweets. 2) Developing an effective topic modeling method for short texts that geographically provides the topic distribution. 3) Designing a spatiotemporal topic-specific influencer user ranking algorithm. 4) Performing extensive experiments to demonstrate the efficacy of our proposed framework. For the third method, we address the challenge of bot detection on social media platform X, where there's an inherent imbalance between genuine users and bots, a key factor leading to biased classifiers. Our approach leverages the rich structure of hypergraphs to represent X users and their interactions, providing a novel foundation for effective bot detection. The contributions of our work include: 1) Introducing a hypergraph representation of the X platform, where user accounts are nodes and their interactions form hyperedges, capturing the intricate relationships between users. 2) Developing HyperSMOTE to generate synthetic bot accounts within the hypergraph, ensuring a balanced training dataset while preserving the hypergraph's structure and semantics. 3) Designing a hypergraph neural network specifically for bot detection, utilizing node and hyperedge information for accurate classification. 4) Conducting comprehensive experiments to validate the effectiveness of our methods, particularly in scenarios with pronounced class imbalances. For the fourth method, we introduce a Hypergraph Convolutional Network model for classifying mental health advice in Arabic tweets. Our model distinguishes between valid and misleading advice, leveraging high-order word relations in short texts through hypergraph structures. Our extensive experiments demonstrate its effectiveness over existing methods. The key contributions of our work include: 1) Developing a hypergraph-based model for short text multiclass classification, capturing complex word relationships through hypergraph convolution. 2) Defining four types of hyperedges to encapsulate local and global contexts and semantic similarities in our dataset. 3) Conducting comprehensive experiments in which the proposed model outperforms several baseline models in classifying Arabic tweets, demonstrating its superiority. For the fifth method, we extended our previous Hypergraph Convolutional Network (HCN) model to be tailored for sarcasm detection across multiple low-resource languages. Our model excels in interpreting the subtle and context-dependent nature of sarcasm in short texts by exploiting the power of hypergraph structures to capture complex, high-order relationships among words. Through the construction of three hyperedge types, our model navigates the intricate semantic and sentiment differences that characterize sarcastic expressions. The key contributions of our research are as follows: 1) A hypergraph-based model was adapted for the task of sarcasm detection in five short low-resource language texts, allowing the model to capture semantic relationships and contextual cues through advanced hypergraph convolution techniques. 2) Introducing a comprehensive framework for constructing hyperedges, incorporating short text, semantic similarity, and sentiment discrepancy hyperedges, which together enrich the model's ability to understand and detect sarcasm across diverse linguistic contexts. 3) The extensive evaluations reveal that the proposed hypergraph model significantly outperforms a range of established baseline methods in the domain of multilingual sarcasm detection, establishing new benchmarks for accuracy and generalizability in detecting sarcasm within low-resource languages. / Doctor of Philosophy / In the digital era, social media platforms are not just tools for communication but vast networks where billions of messages, opinions, and pieces of advice are exchanged every day. Navigating through this massive data to identify influential content, detect misleading information, or understand subtle expressions like sarcasm presents a significant challenge. Traditional methods often struggle to grasp the complex relationships and nuances embedded within the data. This dissertation introduces innovative approaches using hypergraphs—a type of network representation that captures complex interactions more effectively than traditional network models. The research presented explores six distinct applications of hypergraphs in social media analysis, each addressing a unique challenge: 1) The identification of influential users and content specific to certain topics, extending beyond general influence to understand context-driven impact. 2) The incorporation of time and location to detect influential content, recognizing that relevance can significantly vary by these factors. 3) Addressing the issue of imbalanced data in bot detection, where genuine user interactions are overwhelmed by automated accounts, through novel data augmentation techniques. 4) Classifying mental health advice in Arabic tweets to differentiate between valid and misleading information is crucial, given the subject's sensitivity. 5) Detecting sarcasm in low-resource languages is particularly challenging due to its subtle and context-dependent nature. 6) Predicting metro passenger ridership at each metro station is challenging due to the constantly evolving nature of the network and passengers going in and out of stations. This work contributes to the field by demonstrating the capability of hypergraphs to provide more fine-grained and context-aware analyses of social media content. Through extensive experimentation, it showcases the effectiveness of these methods in improving detection, classification, and prediction tasks. The findings not only advance our technical understanding and capabilities in social media analysis but also have practical implications for enhancing the reliability and usefulness of information disseminated on these platforms.

abstract: Graph is a ubiquitous data structure, which appears in a broad range of real-world scenarios. Accordingly, there has been a surge of research to represent and learn from graphs in order to accomplish various machine learning and graph analysis tasks. However, most of these efforts only utilize the graph structure while nodes in real-world graphs usually come with a rich set of attributes. Typical examples of such nodes and their attributes are users and their profiles in social networks, scientific articles and their content in citation networks, protein molecules and their gene sets in biological networks as well as web pages and their content on the Web. Utilizing node features in such graphs---attributed graphs---can alleviate the graph sparsity problem and help explain various phenomena (e.g., the motives behind the formation of communities in social networks). Therefore, further study of attributed graphs is required to take full advantage of node attributes. In the wild, attributed graphs are usually unlabeled. Moreover, annotating data is an expensive and time-consuming process, which suffers from many limitations such as annotators’ subjectivity, reproducibility, and consistency. The challenges of data annotation and the growing increase of unlabeled attributed graphs in various real-world applications significantly demand unsupervised learning for attributed graphs. In this dissertation, I propose a set of novel models to learn from attributed graphs in an unsupervised manner. To better understand and represent nodes and communities in attributed graphs, I present different models in node and community levels. In node level, I utilize node features as well as the graph structure in attributed graphs to learn distributed representations of nodes, which can be useful in a variety of downstream machine learning applications. In community level, with a focus on social media, I take advantage of both node attributes and the graph structure to discover not only communities but also their sentiment-driven profiles and inter-community relations (i.e., alliance, antagonism, or no relation). The discovered community profiles and relations help to better understand the structure and dynamics of social media. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

Graph Convolutional Networks (GCNs) draws significant attention due to its power of representation learning on graphs. Recent works developed frameworks to train deep GCNs. Such works show impressive results in tasks like point cloud classification and segmentation, and protein interaction prediction. While for large-scale graphs, doing full-batch training by GCNs is still challenging especially when GCNs go deeper. By fully analyzing a clustering-based mini-batch training algorithm ClusterGCN, we propose random partition which is a more efficient and effective method to implement mini-batch training. Besides, selecting different permutation invariance function (such as max, mean or add) for neighbors’ information aggregation will result in every different results. Therefore, we propose to alleviate it by introducing a novel Generalized Aggregation Function. In this thesis, I analyze the drawbacks caused by ClusterGCN and discuss about its limits. I further compare the performance of ClusterGCN with random partition and the final experimental results show that simple random partition outperforms ClusterGCN with very obvious advantageous for node property prediction task. For the techniques which are commonly used to make GCNs go deeper, I demonstrate a better way of applying residual connections (pre-activation) to stack more layers for GCNs. Last, I show the complete work of training deeper GCNs with generalized aggregators and display the promising results over several datasets from the Open Graph Benchmark (OGB).

Graph signal processing is a field concerning theprocessing of graphs with data associated to their vertices, oftenin the purpose of modeling networks. One area of this fieldthat has been under research in recent years is the developmentof frameworks for learning graph topologies from such data.This may be useful in situations where one wants to representa phenomenon with a graph, but where an obvious topologyis not available. The aim of this project was to evaluate theusefulness of one such proposed learning framework in thecontext of image segmentation. The method used for achievingthis consisted in constructing graph representations of imagesfrom said framework, and clustering their vertices with anestablished graph-based segmentation algorithm. The resultsdemonstrate that this approach may well be useful, although theimplementation used in the project carried out segmentationssignificantly slower than state of the art methods. A numberof possible improvements to be made regarding this aspect arehowever pointed out and may be subject for future work. / Grafsignalbehandling är ett ämnesområde vars syfte är att behandla grafer med data associerat till deras noder, ofta inom nätverksmodelleringen. Inom detta område pågår aktiv forskning med att utveckla tekniker för att konstruera graftopologier från sådana data. Dessa tekniker kan vara användbara när man vill representera ett fenomen med grafer, men då uppenbara grafstrukturer inte finns tillgängliga. Syftet med detta projekt var att utvärdera användbarheten hos en sådan teknik när den appliceras inom bildsegmentering. Metoden som användes bestod i att konstruera grafrepresentationer av bilder med hjälp av denna teknik, för att sedan behandla dessa med en etablerad, grafbaserad segmenteringsalgoritm. Resultaten påvisar att detta tillvägagångssätt under rätt förutsättningar kan producera tillfredsställande bildsegmenteringar. Dock är implementeringen som nyttjats i projektet betydligt långsammare än de metoder som vanligen används inom området. Ett antal förslag till prestandaförbättring utpekas, och kan vara föremål för framtida studier. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

Graph structures can often be used to describecomplex data sets. In many applications, the graph structureis not known but must be inferred from data. Furthermore, realworld data is often naturally described by sparse graphs. Inthis project, we have aimed at recreating the results describedin previous work, namely to learn a graph that can be usedfor prediction using an ℓ1-penalised LASSO approach. We alsopropose different methods for learning and evaluating the graph. We have evaluated the methods on synthetic data and real-worldSwedish temperature data. The results show that we are unableto recreate the results of the previous research team, but wemanage to learn sparse graphs that could be used for prediction. Further work is needed to verify our results. / Grafstrukturer kan ofta användas för att beskriva komplex data. I många tillämpningar är grafstrukturen inte känd, utan måste läras från data. Vidare beskrivs verklig data ofta naturligt av glesa grafer. I detta projekt har vi försökt återskapa resultaten från ett tidigare forskningsarbete, nämligen att lära en graf som kan användas för prediktion med en ℓ1pennaliserad LASSO-metod. Vi föreslår även andra metoder för inlärning och utvärdering av grafen. Vi har testat metoderna  på syntetisk data och verklig temperaturdata från Sverige.  Resultaten visar att vi inte kan återskapa de tidigare forskarnas resultat, men vi lyckas lära in glesa grafer som kan användas för prediktion. Ytterligare arbete krävs för att verifiera våra resultat. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

This dissertation addresses two fundamental problems in computer vision—namely, multitarget tracking and event recognition in videos. These problems are challenging because uncertainty may arise from a host of sources, including motion blur, occlusions, and dynamic cluttered backgrounds. We show that these challenges can be successfully addressed by using a multiscale, volumetric video representation, and taking into account various constraints between events offered by domain knowledge. The dissertation presents our two alternative approaches to multitarget tracking. The first approach seeks to transitively link object detections across consecutive video frames by finding the maximum independent set of a graph of all object detections. Two maximum-independent-set algorithms are specified, and their convergence properties theoretically analyzed. The second approach hierarchically partitions the space-time volume of a video into tracks of objects, producing a segmentation graph of that video. The resulting tracks encode rich contextual cues between salient video parts in space and time, and thus facilitate event recognition, and segmentation in space and time. We also describe our two alternative approaches to event recognition. The first approach seeks to learn a structural probabilistic model of an event class from training videos represented by hierarchical segmentation graphs. The graph model is then used for inference of event occurrences in new videos. Learning and inference algorithms are formulated within the same framework, and their convergence rates theoretically analyzed. The second approach to event recognition uses probabilistic first-order logic for reasoning over continuous time intervals. We specify the syntax, learning, and inference algorithms of this probabilistic event logic. Qualitative and quantitative results on benchmark video datasets are also presented. The results demonstrate that our approaches provide consistent video interpretation with respect to acquired domain knowledge. We outperform most of the state-of-the-art approaches on benchmark datasets. We also present our new basketball dataset that complements existing benchmarks with new challenges. / Graduation date: 2011 / Access restricted to the OSU Community at author's request from May 12, 2011 - May 12, 2012

<p dir="ltr">Urban traffic networks encompass the collection and interlinking of urban entities, including but not limited to road networks, congested segments, mobile populations, and emergency occurrences. These entities facilitate daily human activities, support economic endeavors, and influence the trajectory of societal advancement. Comprehending the characteristics and anticipating the evolution of dynamic urban traffic networks have been fundamental building blocks in urban science. Typical examples include the primal and dual representations of road networks, the macroscopic fundamental diagram applied to congested roads, and models on the spread of diseases. Current seminal studies either devise physics metrics and models to elucidate universal traits of urban traffic networks, or exploit data-driven approaches to depict the urban landscape using vast amounts of urban data. However, these physics and data-driven methods primarily function separately, resulting in a lack of a comprehensive framework to accurately and interpretably (1) characterize the topology and dynamics of urban traffic networks; and (2) forecast the evolution of dynamics within urban traffic networks.</p><p dir="ltr">In this dissertation, we develop physics-informed graph learning methods to learn and forecast urban traffic networks in manners that are accurate, interpretable, adaptable, and applicable, aiming to advance urban science theories and support urban decision-making processes.</p><p dir="ltr">In Chapters 3 and 4, we explore novel physics knowledge of urban traffic networks in terms of new metrics and equations. In Chapter 3, we define new morphological metrics for urban road networks. Specifically, we present a network metric called spatial homogeneity (SH), which gauges the topological similarities among urban road networks using graph neural networks. Employing this metric, we analyze 11,790 urban road networks across 30 cities worldwide. Our findings reveal the inherent correlations between innercity SH, gross domestic product, and population growth. Furthermore, we quantify learning trajectories between cities from intercity SH and connect them with existing qualitative urban studies. In Chapter 4, we establish new differential equations governing dynamic urban traffic. Through a symbolic regression-based learning approach, we come up with network-level dynamic traffic equations (NDTEs), which capture time-of-day traffic flow and traffic occupancy dynamics. The advantages of NDTEs are twofold: (1) all input variables are easily obtainable; (2) they incorporate vehicle count-related variables. Our experiments on road networks in Zurich and Toronto demonstrate that the generated NDTEs offer enhanced fitting accuracy compared to the baseline model while maintaining a moderate level of equation complexity.</p><p dir="ltr">In Chapters 5, 6, and 7, we harness physics knowledge to devise graph learning approaches for urban prediction and imputation. In Chapter 5, we present NMFD-GNN, a physics-informed machine learning method that integrates the network macroscopic fundamental diagram and the graph neural network for traffic state imputation. Our approach is the first physics-informed machine learning model specifically designed for real-world traffic networks with multiple roads, while existing studies have primarily focused on individual road corridors. In Chapter 6, we develop the spatio-temporal physics ordinary differential equation (ST-PODE), which connects PODEs with spatio-temporal neural networks. ST-PODE is composed of the spatio-temporal neural network module, the PODE module, and the state transition module. We downscale our focus to the prediction of morning traffic patterns and evaluate our models using datasets from the Bay Area and Los Angeles. In Chapter 7, we address the multiwave COVID-19 prediction challenge on urban mobility networks. The proposed social awareness-based graph neural network (SAB-GNN) models the evolution of public awareness across multiple pandemic waves as an exponential function with learnable parameters. We employ the mobility, web search, and infection data in Tokyo from April 2020 to May 2021 to validate its performance. </p><p dir="ltr">The intended audiences of this dissertation comprise colleagues in the fields of artificial intelligence, urban science, transportation engineering, and network science. Our goal is to offer instructive insights to the community to (1) explore universal properties, (2) foresee future evolution, and (3) interpret models and results using massive graph-structured data in urban traffic networks.</p>

Knowledge Graphs are fascinating concepts in machine learning as they can hold usefully structured information in the form of entities and their relations. Despite the valuable applications of such graphs, most knowledge bases remain incomplete. This missing information harms downstream applications such as information retrieval and opens a window for research in statistical relational learning tasks such as node classification and link prediction. This work proposes a deep learning framework based on existing relational convolutional (R-GCN) layers to learn on highly multi-relational data characteristic of realistic knowledge graphs for node property classification tasks. We propose a deep and improved variant, Deep-RGCNs, with dense and residual skip connections between layers. These skip connections are known to be very successful with popular deep CNN-architectures such as ResNet and DenseNet. In our experiments, we investigate and compare the performance of Deep-RGCN with different baselines on multi-relational graph benchmark datasets, AIFB and MUTAG, and show how the deep architecture boosts the performance in the task of node property classification. We also study the training performance of Deep-RGCNs (with N layers) and discuss the gradient vanishing and over-smoothing problems common to deeper GCN architectures.

The field of generative graph models has seen increased popularity during recent years as it allows us to model the underlying distribution of a network and thus recreate it. From allowing anonymization of sensitive information in social networks to data augmentation of rare diseases in the brain, the ability to generate synthetic data has multiple applications in various domains. However, most current methods face the bottleneck of trying to generate the entire adjacency matrix and are thus limited to graphs with less than tens of thousands of nodes. In contrast, large real-world graphs like social networks or transaction graphs can extend significantly beyond these boundaries. Furthermore, the current scalable approaches are predominantly based on stochasticity and do not capture local structures and communities. In this paper, we propose Graphwave Edge-Linking CELL or GELCELL, a novel three-step architecture for generating graphs at scale. First, instead of constructing the entire network, GELCELL partitions the data and generates each cluster separately, allowing for efficient and parallelizable training. Then, by encoding the nodes, it trains a classifier to predict the edges between the partitions to patch them together, creating a synthetic version of the original large graph. Although it does suffer from some limitations due to necessary constraints on the cluster sizes, the results showed that GELCELL, given optimized parameters, can produce graphs with reasonable accuracy on all data tested, with the largest having 400 000 nodes and 1 000 000 edges. / Generativa grafmodeller har sett ökad popularitet under de senaste åren eftersom det möjliggör modellering av grafens underliggande distribution, och vi kan på så sätt återskapa liknande kopior. Förmågan att generera syntetisk data har ett flertal applikationsområden i en mängd av områden, allt från att möjligöra anonymisering av känslig data i sociala nätverk till att utöka mängden tillgänglig data av ovanliga hjärnsjukdomar. Dagens metoder har länge varit begränsade till grafer med under tiotusental noder, då dessa inte är tillräckligt skalbara, men grafer som sociala nätverk eller transaktionsgrafer kan sträcka sig långt utöver dessa gränser. Dessutom är de nuvarande skalbara tillvägagångssätten till största delen baserade på stokasticitet och fångar inte lokala strukturer och kluster. I denna rapport föreslår vi ”Graphwave EdgeLinking CELL” eller GELCELL, en trestegsarkitektur för att generera grafer i större skala. Istället för att återskapa hela grafen direkt så partitionerar GELCELL all datat och genererar varje kluster separat, vilket möjliggör både effektiv och parallelliserbar träning. Vi kan sedan koppla samman grafen genom att koda noderna och träna en modell för att prediktera länkarna mellan kluster och återskapa en syntetisk version av originalet. Metoden kräver vissa antaganden gällande max-storleken på dess kluster men är flexibel och kan rymma domänkännedom om en specifik graf i form av informerad parameterinställning. Trots detta visar resultaten på varierade träningsdata att GELCELL, givet optimerade parametrar, är kapabel att genera grafer med godtycklig precision upp till den största beprövade grafen med 400 000 noder och 1 000 000 länkar.