OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation

6 likes3,498 views

This document presents OMNI-Prop, a new algorithm for node classification on graphs that can handle arbitrary label correlation types. OMNI-Prop calculates variables representing the likelihood of node labels and propagates these values to achieve classification. It runs in linear time per iteration and converges on any graph. Experimental results show OMNI-Prop outperforms other methods on various datasets.

OMNI-?‐Prop:
?
Seamless
?Node
?Classi?ca/on
?
on
?Arbitrary
?Label
?Correla/on
Yuto
?Yamaguchi?
?
Christos
?Faloutsos?
?
Hiroyuki
?Kitagawa?
?

?
?U.
?of
?Tsukuba
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??CMU
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
1
?
?

Node
?Classi?ca/on
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
2
Find: correct labels of unlabeled nodes
?
?

Our
?focus
?–
?Label
?correla/on
?types
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
3
Various
?label
?correla5on
?types
Homophily
Heterophily
Mixed
?
?Exis/ng
?algorithms:
?

?prior
?assump/on
?needed
?

?e.g.)
?label
?propaga*on
?[Zhu+,2003]
?

?
?
?assumes
?homophily
?

?
?
?Our
?algorithm:
?

?no
?prior
?assump/on
?

Contribu/ons
Propose
?OMNI-?‐Prop:
?a
?node
?classi?ca/on
?algorithm
?
?? Seamless
?and
?Accurate
?
–? good
?accuracy
?on
?arbitrary
?label
?correla/on
?
?? Fast
?
–? each
?itera/on
?is
?linear
?on
?input
?graph
?size
?
–? convergence
?guarantee
?
?? (Quasi-?‐parameter
?free)
?-?‐
?omiZed
?in
?this
?talk
?for
?brevity
?
?
–? Just
?one
?parameter
?with
?default
?value
?1
?
–? No
?parameter
?to
?tune
?
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
4

ALGORITHM
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
5

Basic
?Idea
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
6

?
If most of the neighbors of a node have the same label,
then the rest also have the same label.
?
Most
?neighbors
?are
?the
?same
?
à?
?the
?rest
?is
?also
?the
?same
Neighbors
?have
?di?erent
?labels
?
à?
?say
?nothing

?
?
?
?

How
?it
?works?
?
?
?
?
?
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
7
?? sij:
?How
?likely
?node
?i
?has
?label
?j
?
?? tij:
?How
?likely
?the
?neighbors
?of
?node
?i
?have
?label
?j
Calculate
?two
?variables
?recursively
male
male
male
unknown
male
male
male
male?
most
?friends
?
are
?males!
I
?am
?a
?male
s-?‐propaga5on
t-?‐propaga5on
s
s
s
s
??
?aggrega/on
?of
?t
??
?aggrega/on
?of
?s
t
t
t
t
you
?are
?
probably
?males
see
?paper
?for
?details
?
?

THEORETICAL
?RESULTS
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
8

Complexity
?and
?Convergence
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
9
*
?K:
?#
?labels
?
?
?
?N:
?#
?nodes
?
?
?
?M:
?#
?edges
?
[Theorem 1 - complexity]
The time complexity of each iteration
of OMNI-Prop is O(K(N+M))
[Theorem 2 - convergence]
OMNI-Prop always converges on arbitrary graphs

Theore/cal
?connec/on
?to
?SSL
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
10
Label
?Propaga/on
?[Zhu+,
?2003]
Original
?graph
Twin
?graph
[Theorem 3 - equivalence]
The special case of OMNI-Prop is equivalent
to LP on twin graph

EXPERIMENTAL
?RESULTS
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
11

Experimental
?Segngs
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
12
Datasets
Baselines
?? Label
?Propaga/on
?[Zhu+,
?2003]
?
?? Belief
?Propaga/on

Results
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
13
OMNI-?‐Prop
?(red
?line)
?almost
?always
?wins
?on
?all
?datasets
upper
?
?
be[er

Summary
?? Proposed
?OMNI-?‐Prop
?
–? Seamless
?NL
?on
?arbitrary
?label
?correla/on
?
–? Fast
?
–? (Quasi-?‐parameter
?free)
?
?? Theore/cally
?
–? Linear
?on
?input
?size
?for
?each
?itera/on
?
–? Always
?converges
?on
?arbitrary
?graphs
?
–? special
?case
?=
?LP
?
?? Experimentally
?
–? Almost
?always
?wins
?on
?all
?5
?datasets
15/01/29
Yuto
?Yamaguchi
?-?‐
?AAAI2015
14

1. The document analyzes patterns in interactive tagging networks on Twitter, contrasting them with traditional resource tagging networks and examining reciprocity. 2. It finds that interactive tagging networks on Twitter consist of broad folksonomies with many users categorizing others, unlike narrow folksonomies where users primarily tag their own resources. 3. Larger multiplicity of tags between users and friendship-related tags are more likely to be reciprocated in interactive tagging networks.

半教师あり学习syou6162

The document introduces several approaches to semi-supervised learning, including self-training, multi-view algorithms like co-training, generative models using EM, S3VMs which extend SVMs to incorporate unlabeled data, and graph-based algorithms. Semi-supervised learning can make use of large amounts of unlabeled data together with smaller amounts of labeled data to build accurate predictive models in domains where labeling data is expensive.

When Does Label Propagation Fail? A View from a Network Generative Model@ERAT...Yuto Yamaguchi

Bridging Relational Learning Algorithms@ビッグデータ基盤勉強会Yuto Yamaguchi

Tensor Decomposition with Missing IndicesYuto Yamaguchi

This document proposes a new tensor decomposition model to handle cases where tensor indices are partially missing. The model treats indices as latent variables and uses a variational MAP-EM algorithm to infer missing indices and learn tensor decomposition parameters. Experiments on synthetic and real-world Twitter data show the model performs well when the number of samples is large or the missing ratio is not very high, outperforming alternative approaches that cannot handle missing indices.

When Does Label Propagation Fail? A View from a Network Generative ModelYuto Yamaguchi

The document proposes a Partially Labeled Stochastic Block Model (PLSBM) as a probabilistic generative model for networks with some labeled nodes. It proves the relationship between label propagation (LP) and the Stochastic Block Model (SBM) through PLSBM. Specifically, it shows that the solution to LP is identical to maximum likelihood estimation under PLSBM when the label ratio is uniform, edge probabilities are uniform within and between labels, and the network is assortative. When these conditions do not hold, LP is shown to fail both theoretically and experimentally.

Robust Large-Scale Machine Learning in the CloudYuto Yamaguchi

SocNL: Bayesian Label Propagation with ConfidenceYuto Yamaguchi

This document proposes a new algorithm called SocNL for node classification in graphs. SocNL incorporates classification confidence by assigning confidence scores when labeling nodes based on their connections. It assumes that connected nodes will share labels, and nodes with many labeled neighbors can be labeled confidently. SocNL is proven to converge, and is theoretically equivalent to linear programming or Bayesian inference approaches. Empirical tests on three real-world networks show SocNL achieves higher overall accuracy than competing algorithms.

Online User Location Inference Exploiting Spatiotemporal Correlations in Soci...Yuto Yamaguchi

The document presents a new online and incremental method for inferring user home locations from social media posts. It exploits spatiotemporal correlations in social streams by extracting local words that are correlated to locations over specific time periods. The proposed Online Location Inference Method (OLIM) divides the map into regions, calculates population distributions, and updates local word distributions and user location distributions incrementally as new posts arrive. An evaluation on a Twitter dataset shows it achieves better accuracy than existing batch methods and has lower computational cost per update.

SIGMOD2013勉強会：Social MediaYuto Yamaguchi

Towards Social User Profiling: Unified and Discriminative Influence Model for...Yuto Yamaguchi

The paper presents a unified discriminative influence model (UDI) to infer users' home locations on social networks, specifically addressing challenges of scarce and noisy signals in location data. Using Twitter data, the authors propose two location profiling methods—local and global prediction strategies—and demonstrate that their approach can correctly place 66% of users within a 100-mile error distance. Extensive experiments indicate that the UDI significantly outperforms existing methods for location inference.

The Length of Bridge Ties: Structural and Geographic Properties of Online So...Yuto Yamaguchi

The document explores the relationship between structural properties of online social ties and spatial distance, indicating that individuals closer in proximity are more likely to establish social connections. Results reveal that social links within the core span shorter distances compared to those in the periphery, and interaction levels are higher among closely connected users. The study highlights how spatial constraints impact network structure and social bonds, particularly emphasizing the roles of tie strength and network positioning.

WWW2012勉強会：Information Diffusion in Social NetworksYuto Yamaguchi

滨颁顿贰2012勉强会：Social MediaYuto Yamaguchi

pollination njnjnjnjnjnjjnjnjnjnjnjnjnnjbhg31shagnik

Abzymes mimickers in catalytic reactions at nanoscalesOrchideaMariaLecian

Algebra A BASIC REVIEW INTERMEDICATE ALGEBRAropamadoda

The Emergence of Signatures of AGI: The Physics of LearningCharles Martin

Pushkar camel fest at college campus placementnandanitiwari82528

SCIENCE-G7-Quarter1-Week1-Day5.matatagptxPyumpyum

Molecular biology and pellet weight markednandanitiwari82528

Cryptocurrency and cyber crime PresentationIqraRehaman

Matt Ridley: Economic Evolution and Ideas that have SexConservative Institute / Konzervatívny in?titút M. R. ?tefánika

esmo-academy-2024-pptx-template smyth final.pdfGuillermoGutirrez33

Smart Grids Selected Topics, Advanced Metering InfrastructureFrancisSeverineRugan

Gas Exchange in Insects and structures 01PhoebeAkinyi1

Antibiotic and herbicide Resistance GenesAkshitRawat20

Pneumonia Presentation for CPG Review and MasteryJayricDepalobos

HOW TO FACE THREATS FROM THE FORCES OF NATURE EXISTING ON PLANET EARTH.pdfFaga1939

This article aims to present how to deal with localized or global threats to human beings caused by the forces of nature that exist on planet Earth. The threats to human beings caused by the forces of nature that exist on planet Earth include earthquakes and tsunamis that can affect specific areas of the planet, volcanic eruptions that can affect specific areas of the planet or have a global impact, the cooling of the Earth's core and the inversion of the Earth's magnetic poles, both of which have a global impact. Specific measures are proposed to deal with each of the threats, but in addition to these, it is necessary to create a global structure, a World Organization for Defense Against Natural Disasters with global scope linked to the UN (United Nations) that has the capacity to technically coordinate the actions of countries around the world in dealing with these threats. The creation of this body is absolutely necessary because most of the threats from the forces of nature that exist on planet Earth have a global impact. To carry out its functions, this body must have financial resources from a global fund against natural disasters of global scope to be maintained by all countries on the planet and administered by the UN.

GBSN_ Unit 1 - Introduction to MicrobiologyAreesha Ahmad

OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation

1. OMNI-?‐Prop: ? Seamless ?Node ?Classi?ca/on ? on ?Arbitrary ?Label ?Correla/on Yuto ?Yamaguchi? ? Christos ?Faloutsos? ? Hiroyuki ?Kitagawa? ? ? ?U. ?of ?Tsukuba ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??CMU 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 1 ? ?

2. Node ?Classi?ca/on 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 2 Find: correct labels of unlabeled nodes ? ?

3. Our ?focus ?– ?Label ?correla/on ?types 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 3 Various ?label ?correla5on ?types Homophily Heterophily Mixed ? ?Exis/ng ?algorithms: ? ?prior ?assump/on ?needed ? ?e.g.) ?label ?propaga*on ?[Zhu+,2003] ? ? ? ?assumes ?homophily ? ? ? ?Our ?algorithm: ? ?no ?prior ?assump/on ?

4. Contribu/ons Propose ?OMNI-?‐Prop: ?a ?node ?classi?ca/on ?algorithm ? ?? Seamless ?and ?Accurate ? –? good ?accuracy ?on ?arbitrary ?label ?correla/on ? ?? Fast ? –? each ?itera/on ?is ?linear ?on ?input ?graph ?size ? –? convergence ?guarantee ? ?? (Quasi-?‐parameter ?free) ?-?‐ ?omiZed ?in ?this ?talk ?for ?brevity ? ? –? Just ?one ?parameter ?with ?default ?value ?1 ? –? No ?parameter ?to ?tune ? 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 4

5. ALGORITHM 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 5

6. Basic ?Idea 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 6 ? If most of the neighbors of a node have the same label, then the rest also have the same label. ? Most ?neighbors ?are ?the ?same ? à? ?the ?rest ?is ?also ?the ?same Neighbors ?have ?di?erent ?labels ? à? ?say ?nothing ? ? ? ?

7. How ?it ?works? ? ? ? ? ? 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 7 ?? sij: ?How ?likely ?node ?i ?has ?label ?j ? ?? tij: ?How ?likely ?the ?neighbors ?of ?node ?i ?have ?label ?j Calculate ?two ?variables ?recursively male male male unknown male male male male? most ?friends ? are ?males! I ?am ?a ?male s-?‐propaga5on t-?‐propaga5on s s s s ?? ?aggrega/on ?of ?t ?? ?aggrega/on ?of ?s t t t t you ?are ? probably ?males see ?paper ?for ?details ? ?

8. THEORETICAL ?RESULTS 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 8

9. Complexity ?and ?Convergence 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 9 * ?K: ?# ?labels ? ? ? ?N: ?# ?nodes ? ? ? ?M: ?# ?edges ? [Theorem 1 - complexity] The time complexity of each iteration of OMNI-Prop is O(K(N+M)) [Theorem 2 - convergence] OMNI-Prop always converges on arbitrary graphs

10. Theore/cal ?connec/on ?to ?SSL 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 10 Label ?Propaga/on ?[Zhu+, ?2003] Original ?graph Twin ?graph [Theorem 3 - equivalence] The special case of OMNI-Prop is equivalent to LP on twin graph

11. EXPERIMENTAL ?RESULTS 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 11

12. Experimental ?Segngs 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 12 Datasets Baselines ?? Label ?Propaga/on ?[Zhu+, ?2003] ? ?? Belief ?Propaga/on

13. Results 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 13 OMNI-?‐Prop ?(red ?line) ?almost ?always ?wins ?on ?all ?datasets upper ? ? be[er

14. Summary ?? Proposed ?OMNI-?‐Prop ? –? Seamless ?NL ?on ?arbitrary ?label ?correla/on ? –? Fast ? –? (Quasi-?‐parameter ?free) ? ?? Theore/cally ? –? Linear ?on ?input ?size ?for ?each ?itera/on ? –? Always ?converges ?on ?arbitrary ?graphs ? –? special ?case ?= ?LP ? ?? Experimentally ? –? Almost ?always ?wins ?on ?all ?5 ?datasets 15/01/29 Yuto ?Yamaguchi ?-?‐ ?AAAI2015 14

狠狠撸

OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation

Recommended

More Related Content

More from Yuto Yamaguchi (6)

Recently uploaded (20)

OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation